Problem Detail: Let $Sigma = {0,1}$. For every word $w in Sigma^*$, let $|w|_0$ and $|w|_1$ denote the count of 0’s and 1’s, respectively, in $w$. Let $L$ be the language $$L = { w in Sigma^* mid |w|_0 gt |w|_1 + 2 text{ or } |w|_1 gt |w|_0 + 2}$$ Prove or disprove whether $L$ is regular.
Asked By : Harshil
Answered By : Shaull
Recall that regular languages are closed under complementation. That is, if $L$ is regular, than so is $overline{L}=Sigma^*setminus L$. Thus, if you manage to prove that $overline{L}$ is not regular, then $L$ is not regular as well. Observe that $$begin{align} overline{L} &= {win {0,1}^*: |w|_0le |w|_1+2 wedge |w|_1le |w|_0+2} &={w:|w|_1-2le |w|_0le |w|_1+2} end{align} $$ Assume by way of contradiction that $overline{L}$ is regular, then by the pumping lemma, there exists a pumping constant $p$. Consider the word $0^p1^pin overline{L}$, then (by standard pumping-lemma arguments) there exists some $ile p$ such that $0^{p+ki}1^pin overline{L}$ for every natural $k$. Choose $k=5$ (any number greater than 2 will work), then $p+5i>p+2$, and therefore $0^{p+ki}1^pnotin overline{L}$, which is a contradiction.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/14323
