2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Every non-empty ω-regular language contains an ultimately periodic word. $\endgroup$
    – The User
    Oct 20, 2013 at 21:59

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ thank you, I was just considering finite repitions, but yes just discard the tail and "pump" infinitely often works! $\endgroup$
    – StefanH
    Oct 20, 2013 at 20:35
  • 1
    $\begingroup$ A shorter formulation of this answer. Every nonempty $\omega$-regular language contains an ultimately periodic word. Such word cannot have all the words as factors. $\endgroup$
    – J.-E. Pin
    Oct 21, 2013 at 14:10
  • $\begingroup$ @joel-david-hamkins I did refer to nonempty languages :=) $\endgroup$
    – J.-E. Pin
    Oct 21, 2013 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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