Using group presentation, does $\langle A = a^3, 1 = A^2 \rangle$ relate to $\langle A = a^2, 1 = A^3\rangle$?

Question

Let $G = \langle A = a^3, 1 = A^2 \rangle$ relate to $H = \langle A = a^2, 1 = A^3\rangle$ be two "group presentations" namely for:

$$ \begin{matrix} \cdot & A & a & a^2 & 1 & Aa & Aa^2 \\ A & 1 & Aa & Aa^2 & A & a & a^2\\ a & \dots \\ a^2 \\ 1 \\ A a \\ \vdots \end{matrix} $$

In other words the structure they induce is indeed finite. Though I'm not sure if it's a group. That's okay, I'll work with whatever structure it naturally is in general.

They come from these two smallest grammars:

$$ G = \{S \to AA, A \to aaa \}, \\ H = \{S \to AAA, A \to aa \}, $$

namely by direct translation and identifying $\rightarrow$ with $=$ and $S$ with $1$.

Can we tell if the structures are isomorphic or not? If not, it simply means you have a finite set of isomorphism classes of straight-line grammar associated structures.

Another question: how do they relate to inefficient grammars for the same string $s = a^6$, such as $I = \{ S \to aaAa, A \to aaa \}$ and their respective groups?

---

Note that in the group constructed, $x = y$ iff they expand to the same string, thus you may or may not have $\alpha \beta = \beta \alpha$ in general, but you do when $\Sigma = \{a\}$ is singleton, because everything commutes in that case.

Answer 1

Both $G$ and $H$ are isomorphic to the cyclic group $\mathbb{Z}_6$, and generated by $a$.

An isomorphism between them is fully determined just by sending $a$ to $a$ (to the generating element in $\mathbb{Z}_6$). Note that this will send $A$ in $G$ to $Aa$ in $H$ and likewise send $A$ in $H$ to $a^2$ in $G$.

The reason why all of this works is because the cyclic groups of orders 2 and 3 are subgroups of the cyclic group of order 6, and $G$ and $H$ have just been phrased to emphasise this fact. If you’re looking at any finite group, you will be able to make as many presentations like these as there are cyclic subgroups of your finite group.

Answer 2

According to the comments above, the two groups are isomorphic. So I conjecture:

If $g, h$ are two straight-line grammars of a string $s$ over $\Sigma = \{a\}$ then their associated groups $G, H$ are such that $G \simeq H$. In particular, the group associated with any string $s = a^n, n \gt 0$ is the cyclic group of order $n$.

The smallest grammar problem is then to compute the smallest presentation of the form:

$$ \langle \text{non-generator} = \text{string of non-generator and generator} \rangle $$

where the cost of the presentation is the sum of the lengths of the right hand sides. I know this format definition needs some work such as it can't include occurrences of $\cdot ^{-1}$, the inverse operator.