An $\omega$-word $s \in \Sigma^\omega$ is eventually periodic if it is of the form $s = uv^\omega$ for finite words $u, v \in \Sigma^*$.

I want to show that the set of all eventually periodic words is not buchi-recognizable.

I do not know how to proceed. My attempt was to find a part of the word and then pump it indefinitely to get something that is not in the language. However, pumping right away does not seem to work since that would give an eventually periodic string again.

  • $\begingroup$ Hint: Let $p_1,p_2, \ldots$ be the infinite sequence of prime numbers and assume that a Buchi automaton with $k$ states exists for your language. Show that either $wab^{p_1}ab^{p_2} \ldots $ is accepted by the Buchi automaton for some $w \in \Sigma^*$ or that $(ab^{p_1}ab^{p_2}a\ldots ab^{p_k})^\omega$ is rejected by the automaton. $\endgroup$ – DCTLib Feb 22 '18 at 9:07

Note that every non-empty Büchi recognizable language contains at least one eventually periodic word and that the class of all Büchi recognizable languages is closed under complement. Thus, if the language $L = \{w \in \Sigma^\omega \mid w \text{ is eventually periodic}\}$ was Büchi recognizable its complement $L^C$ is also Büchi recognizable but of course contains no eventually periodic word contradicting the first fact I stated.

  • $\begingroup$ Complementing Buchi Automata is non-trivial, though. $\endgroup$ – Agnishom Chattopadhyay Feb 26 '18 at 12:14
  • $\begingroup$ I agree but for this exercise it is a sufficient argument that it is possible. $\endgroup$ – ttnick Feb 26 '18 at 12:24

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.