Proof that the $\omega$-language consisting of all words containing every finite word as a factor is not rational/regular

Question

Let $\eta$ be an $\omega$-word over $X = \{0,1\}$ and let $F_k(\eta)$ denote the factors of $\eta$ of length $k$. Define the following $\omega$-languages $$ L_k := \{ \xi : F_k(\xi) = X^k \} = \{ \xi : \xi \mbox{ has every finite word of length k as an infix} \}. $$ Then define $$ L := \bigcap_{k=1}^{\infty} L_k = \{ \xi : \xi \mbox{ has every finite word as an infix/factor } \}. $$ Now I want to know if $L$ is $\omega$-rational/regular, or Büchi-recognizable. I conjecture not, because no finite state device could check all factors of arbitrary length. The only methods of proof I know is a variant of the pumping lemma for $\omega$-languages which does not work here, because if I pump a word it is not guaranted that the factors get lost. So how could I proof that the set is not rational?

Answer 1

Indeed, your language $L$ is not Büchi-recognizable. To see this, suppose that we have a finite state Büchi automata $M$ that recognizes all the strings in $L$. That is, $M$ is a finite state automata, and when we run $M$ on any string $s\in L$ we visit an accepting state of $M$ infinitely many times. Fix any particular string $s\in L$, so that $s$ is an infinite binary sequence containing every finite binary sequence as an infix substring. Since $s$ is recognized by $M$, it follows just as in the proof of the pumping lemma, that there must be a finite initial segment $u$ of $s$ that gets us to one of the infinitely-visted accepting states for the first time, and then another chunk $w$ of $s$ that gets us from that state to that state again. So $s$ starts out with $uw$ and then continues with the rest of $s$. But we could run the machine $M$ on the string $t=uw^\omega$, meaning $uwww\cdots$, which is a binary string that is not in $L$, since it is eventually periodic. But this string also will visit that accepting state of $M$ infinitely many times, after each successive additional copy of $w$, and so $M$ will also accept $t$. So $M$ recognizes strings outside $L$, and we are done.

This argument amounts just to using the pumping lemma for Büchi machines, which allows the case of infinitely much pumping---you don't need to attach the string at the end like in the finite string pumping lemma, since you know the accepting state must have been visited infinitely many times.