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.

  • $\begingroup$ This is a pure exercise dump. What have you tried? Where did you get stuck? See here for a discussion why we think your question is bad, and here for questions you should check out before asking. Once you include your own attempts, you have posted a question in its own right that can be answered to solve your specific problem. $\endgroup$
    – Raphael
    Sep 16 '13 at 8:21
  • 1
    $\begingroup$ Be nice. This is your only warning. $\endgroup$ Sep 16 '13 at 20:06

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.


@Shaull's solution is perfect.. here's a slightly different version of it...

try to see, that $L$ = $L_1 \cup L_2$


$L_1 = \{ w \in \{0,1\}^* \mid |w|_0 \gt |w|_1 + 2\}$

$L_2 = \{ w \in \{0,1\}^* \mid |w|_1 \gt |w|_0 + 2\}$

now we will go on to show that $L_1$ is not regular using the pumping lemma.

The pumping lemma states that if some $A$ is a regular language, $\exists$ number $p$ (think of it as the number of states of a DFA that recognizes $A$) such that if $s \in A, |s| \geq p$ then $s$ can be divided into $x,y,z$ such that $s=xyz$ and

  1. $\forall i\geq0, xy^iz \in A$
  2. $|y| > 0$
  3. $|xy| \leq p$

Now, we do a proof by contradiction, and assume that $L_1$ is regular.

Now again, see that $L_1 \supset L_{1a} \cdot L_{1b} $


$L_{1a} = \{ w = 0^n1^n \mid n\geq 0\}$ (it has the same number of 0s and 1s)

$L_{1b} = \{ w \in \{1\}^n \mid n\geq 2\}$

i.e. a regular language is closed under union.

Now we will just show that $L_{1a}$ is not regular.

Proof by contradiction: Assume $L_{1a}$ is regular, then there is a DFA, $M$ that accepts $L_{1a}$. Let $p$ be the num of states.

Let $s$ be some word in $L_{1a}$

Let $s = 0^{p+1}1^{p+1}$

$s= xyz$

$|xy| \leq p $ (from defn pumping lemma)

$|xy|$ has just $0$s

$y$ has atleast one $0$ (from defn pumping lemma)

but $xy^2z$ has more $0$s than $1$s $\rightarrow s = xy^2z \notin L_{1a} $

Contradiction!!! this shows $L_{1a}$ is not regular

Then this gives a contradiction that $L_1$ is regular, and finally that shows that $L$ is also not regular.


Not the answer you're looking for? Browse other questions tagged or ask your own question.