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,
5
-
1$\begingroup$ Derek's answer is great, but this is surely contained in the standard book on the subject (eg Word Processing in Groups). I'm voting to close - MO is not a lazy alternative to reading the literature. $\endgroup$– HJRWApr 9, 2014 at 12:53
-
$\begingroup$ I'm sorry if my question looked like an "lazy alternative" to reading literature. However, many people here are not mathematician and we try to get help from experts to understand these kinds of topics out of our knowledge/research area. I have read several times the book Word Processing in groups and the Handbook of computational group theory but sometimes a nice explanation from experts are very helpful. $\endgroup$– Miguel C.Apr 10, 2014 at 15:32
-
$\begingroup$ In that case I would encourage you to include the reading that you have done in the question. If you state that you've read 'Word processing in groups', say, but you're still confused about something, and can explain what that thing is, then you're more likely to get a helpful answer. $\endgroup$– HJRWApr 10, 2014 at 16:09
-
$\begingroup$ Also, let me add that since Mathoverflow (where this question was first posted) is by definition concerned with questions about research-level mathematics, I would (friendlily!) encourage non-mathematicians to start by posting their question on math.SE. Of course, if your question doesn't get an answer there, then trying MO is entirely appropriate. $\endgroup$– HJRWApr 10, 2014 at 16:11
-
$\begingroup$ I get it. Thanks for your comments and recommendations! $\endgroup$– Miguel C.Apr 15, 2014 at 13:13
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
answered Apr 7, 2014 at 11:18
-
$\begingroup$ Thanks, Professor Holt. It is very helpful. $\endgroup$– Miguel C.Apr 7, 2014 at 13:41