# Is the language with at least as many 0 as 1 on any prefix $\omega$ regular?

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.

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.