I would like to know How can we prove that free groups are automatics? and is it possible to determine the number of states that would have a shortlext automatic structure (Word Acceptor and Multipliers) for such groups?
Thanks a lot,
I would like to know How can we prove that free groups are automatics? and is it possible to determine the number of states that would have a shortlext automatic structure (Word Acceptor and Multipliers) for such groups?
Thanks a lot,
Let the group $F$ be freely generated by $X$ with $|X|=n$, and let $A = X \cup X^{-1}$. (All automatic groups are finitely generated.)
The automatic structure is not unique, but in the most natural such structure, the word acceptor automaton accepts the language of all freely reduced words in $A^*$. The minimal deterministic finite state automaton that accepts this language, has $2n+1$ accepting states and a single fail state. One of the accepting states is the initial state, and the others correspond to the elements of $A$, and keep track of the last input letter read. If it reads a subword $aa^{-1}$ for $a \in A$ then it goes into the fail state and stays there.
The language of the multiplier automaton for a fixed $a \in A$ is the set of all pairs $(w,wa)$, where $w$ is a reduced word that does not end in $a^{-1}$, together with all pairs $(wa^{-1},w)$ where $w$ is a reduced word that does not end in $a$. (More precisely, this should be $(w\$,wa)$ and $(wa^{-1},w\$)$, where $\$$ is the padding symbol.) I will leave you to convince yourself that the minimal automaton accepting this language has $2n+3$ states (one of which is an accepting state, and one of which is a dead state).
Since these these automata fulfil all the necessary conditions for an automatic structure, $F$ is an automatic group.