0
$\begingroup$

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.

3 Answers 3

1

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.

4

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.

3

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.