# The set of all eventually periodic words is not Buchi Recognizable?

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.

• 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. – 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.