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?

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

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.

| cite | improve this answer | |
  • $\begingroup$ thank you, I was just considering finite repitions, but yes just discard the tail and "pump" infinitely often works! $\endgroup$ – StefanH Oct 20 '13 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 '13 at 14:10
  • $\begingroup$ @joel-david-hamkins I did refer to nonempty languages :=) $\endgroup$ – J.-E. Pin Oct 21 '13 at 16:17

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.