[Solved]: Prove or disprove whether L is regular

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} &= \{w\in \{0,1\}^*: |w|_0\le |w|_1+2 \wedge |w|_1\le |w|_0+2\} \\ &=\{w:|w|_1-2\le |w|_0\le |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^p\in \overline{L}$, then (by standard pumping-lemma arguments) there exists some $i\le p$ such that $0^{p+ki}1^p\in \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^p\notin \overline{L}$, which is a contradiction.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14323