In chapter 2 of the New Turing Omnibus, the author considers an unknown finite automata with 6 states. Through trial and error, it is deduced that the words 0101, 0100101, 0100100101 are accepted. It is then stated that using the pumping lemma, it can be shown that if 01(001)^n01 is accepted for n=0,1,2,3,4,5 then all strings of the form 01(001)*01 must also be accepted.

I know of the pumping lemma but do not see how the next leap has been made. Why is it sufficient to only test n up (number of states) - 1?


Let the automaton have states $Q$, initial state $q_0$, accepting states $F$, and transition function $\delta$, and suppose that $|Q| = n$. Denote the language that it accepts by $L$.

Suppose that $xy^iz \in L$ for $i = 0,\ldots,n-1$. Denote $p_i = \delta(q_0,xy^i)$. We consider two cases:

  • The states $p_0,\ldots,p_{n-1}$ are all different. In this case, $Q = \{p_0,\ldots,p_{n-1}\}$, and so $\delta(q,z) \in F$ for all $q \in Q$, implying that $\delta(q_0,xy^iz) \in F$ for all $i$, and so $xy^iz \in L$ for all $i$.
  • For some $j < k$, we have $p_j = p_k$. It follows that the sequence $p_i$ is eventually periodic, and so again $xy^iz \in L$ for all $i$.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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