Q:

Word problem in a free group

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.

A:

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.

A:

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.

