Let $L$ be the language of infinite words in $\{0,1\}^\omega$ such that any finite prefix of a word in $L$ has at least as many $0$'s as $1$'s. Is $L$ büchi recognisable?

I think that $L$ is not $\omega$ regular, but standard tricks such as complementation or intersecting with some other language don't seem to work.


1 Answer 1


As you suspected, $L$ is not büchi recognisable/$\omega$-regular. Here is a proof.

Towards a contradiction, suppose $L$ is $\omega$-regular. Then $$L= A_1B_1^\omega\cup A_2B_2^\omega\cup\cdots\cup A_nB_n^\omega$$ for some $n$, where $A_i$ and $B_i$ are regular languages for all $i$.

Consider $s=0^11^10^21^20^31^3\cdots\in L$. WLOG, suppose $s\in A_1B_1^\omega$. Suppose $s=at$, where $a\in A_1$, $t\in B_1^\omega$.

Let $p$ be a pumping length for $B_1$ as in the general version of the pumping lemma for regular languages, as stated here on Wikipedia.

Consider $\ell=1^{\max(|a|, 2p)}$ that appears in $s$. $\ell$ must appear after $a$ since $0^{|a|}$ appears before $\ell$ in $s$. In other words, $\ell$ is a substring of $s$ without $a$, which is $t$. Since $t\in B_1^\omega$, $\ell$ is the concatenation of a nonempty suffix of a word in $B_1$, zero or more words in $B_1$ and a possibly-empty prefix of a word in $B_1$. There are two cases.

  • $\ell$ contains a word in $B_1$.
    Let $g$ be that word, which contains only $1$s.

  • $\ell$ is a suffix of a word in $B_1$ followed by a possibly-empty prefix of a word in $B_1$.
    Hence $B_1$ contains a word that contains at least $\frac{2p}2=p$ consecutive $1$s. Let $uwv$ be such a string, where $w=1^p$.

    We can write $uwv=uxyzv$ for some string $x,y,z$ with $|y|\ge1$ such that $uxy^iz\in B_1$ for all $i\ge0$, thanks to the general version of the pumping lemma. Since $w$ is all $1$s, so is $y$. Hence for $i$ large enough, $uxy^iz$ has more $1$s than $0s$. Let $g$ be such a word, i.e. $g\in B_1$ has more $1$s than $0$s.

In both cases, we have identified a word $g\in B_1$ that has more $1$s than $0$s. Then $ag^\omega\in A_1B_1^\omega\subseteq L$. However, $ag^\omega\notin L$ since its prefix $ag^{|a|+1}$ has more $1$s than $0$s. This is a contradiction.


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.