Subgroup within a syntactic monoid

59 Views Asked by At

So this is the problem I was given. $$$$Show that the syntactic monoid of the language $(aa)^*$ over the alphabet $\{a,b\}$ has $\mathbb{Z}/2\mathbb{Z}$ as a subgroup. $$$$Obviously, the syntactic monoid is isomorphic to the transition monoid of the minimal DFA, so I minimized the automaton as such: $$$$$1^{-1}L=L=L_1\\a^{-1}L_1=a(aa)^*=L_2\\b^{-1}L_1=\emptyset\\a^{-1}L_2=(aa)^*=L_1\\b^{-1}L_2=\emptyset$

and got a transition monoid by $$\begin{array}{c|c|c|} & \text{1} & \text{2} \\ \hline \text{$a$} & 2 & 1 \\ \hline \text{$b$} & - & - \\ \hline \text{$aa$} & 1 & 2 \\ \hline \end{array}$$ $ab\rightarrow a\\ba\rightarrow b\\bb\rightarrow b.$ $$$$My concern is that I don't know how this translates into subgroups or where I'm supposed to be pulling $\mathbb{Z}/2\mathbb{Z}$ from.

1

There are 1 best solutions below

0
On BEST ANSWER

You are almost there. Note that $aa$ is the identity map on $\{1,2\}$ and hence is syntactically equivalent to the empty word $1$. Thus, in the syntactic monoid (call it $M$), you can write $a^2 = 1$. Now, $\{1, a\}$ is a submonoid of $M$ and is actually a group isomorphic to $\mathbb{Z}/2\mathbb{Z}$.