Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Can the word problem in a free group be solved by a finite state automaton? I know it can be solved by a pushdown automaton.

share|improve this question
add comment

3 Answers 3

up vote 3 down vote accepted

It cannot. Consider the free group with generator $a$, and let $b$ be its inverse, and let's say you want to accept every string that is equivalent to $ab$. This is equivalent to the language $\{w \in \{a,b\}^* ~|~ n_a(w) = n_b(w) \}$. That is, the set of strings with the same number of $a$'s and $b$'s.

Let's use the Pumping Lemma to prove that this language isn't regular. Let $p$ be the pumping length. The string $a^pb^p$ is in the language, and we can break it into $xyz$, where $|y| \geq 1$, $|xy| \leq p$. In other words, $y$ consists only of $a$'s, so $y = a^{|y|}$. If the pumping lemma were true for this language, then $xy^iz$ would also be in the language, for all $i \in \mathbb{N}$. This isn't the case -- for example, $xy^2z$ isn't in the language. So, this language ain't regular.

So, no, a DFA can't solve the word problem for free groups. It can't even recognize the unit element.

share|improve this answer
add comment

It is not hard to prove that the word problem of a group $G$ is the language of a finite state automaton if and only if $G$ is finite. If $G$ is finite, then you can use any generating set for $G$ as alphabet, and label the states by the elements of the groups, with identity element as start state and only accepting state, and the transitions given by the group multiplication table.

Conversely if the word problem for $G$ is the language of a finite automaton, then words $u$ and $v$ in the group generators representing distinct elements of $G$ must lead to distinct states, since otherwise the automaton would be forced to accept the word $uv^{-1}$. So there are at least $|G|$ states, and hence $G$ is finite.

share|improve this answer
add comment

You can very easily prove using the idea of the pumping lemma that the set of words which denote the unit element in the free group with one element. Fix a candidate automaton which recognizes the language, let $N$ be the number of states it has, and consider words of the form $x^nx^{-n}$ with $n\gg N$.

Exactly the same argument also works in a free group of any rank, of course.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.