Quaternion group as a Freegroup

The Quaternion group can be defined as follows $\{(a,b) : a^4=e,b^4=e,a^2=b^2,ab=ba^3\}$. Let's be practical and set a=i, b=j and let's implement this in Mathematica.

The following Mathematica code

$r:=\{ \text{iiii} \to \text{""} , \text{jjjj} \to \text{""} ,\text{ii} \to \text{jj},\text{ij} \to \text{jiii}\}$

$f[\text{x_}]:=\text{StringReplace}[x,r]$

$\text{NestList}[f,\text{"ijij"},5]$

yields:

$\{\text{ijij},\text{jiiijiii},\text{jjjjiiijji},\text{jjjiiiji},\text{jjjjjjiiii},\text{jj}\}$


Let me explain. The variable $r$ is a list which contains four ( production ) rules, i.e.:
$\text{iiii} \to \text{""}$ - Says that $i^4 = 1$.
$\text{jjjj} \to \text{""}$ - Says that $j^4 = 1$.
$\text{ii} \to \text{jj}$ - Says that $i^2 = j^2$. And $i^2=-1$ as we know.
$\text{ij} \to \text{jiii}$ - Says that $ij = jiii$. Or $ij=-ji$.

The command $f[\text{x_}]:=\text{StringReplace}[x,r]$ takes a string as input and applies the production rules once from left to right. This command can be repeated until the input string no longer changes. In the case of $"ijij"$ it took $5$ times and the input and resp. outputs were as follows.

$\{\text{ijij}$,
$\text{jiiijiii}$,
$\text{jjjjiiijji}$,
$\text{jjjiiiji}$,
$\text{jjjjjjiiii}$,
$\text{jj}\}$

As you see $(ij)^2=k^2$ is correctly evaluated to $j^2=-1$.

From here on it's fairly easy to generate all elements from the quaternion group by string concatenation and applying the production rules.