Proving a Language is not Regular using the Pumping Lemma

Consider the following language definition

$\begin{equation*} L = \{ w \in \{0, 1\}^* : w \text{ contains the same number of 010 substrings as 111} \} \end{equation*}$

This language is not regular. This article explores a step by step approach to prove this by contradicting the Pumping Lemma for Regular languages.

Assumption

Suppose to the contrary $L$ is regular and $p$ be its pumping length. Let $\#_{111}w$ and $\#_{010}w$ denote the number of $111$ and $010$ substrings in $w$ respectively.

Choosing a string

A string $w$ has to be chosen such that it satisfies the following two conditions

$\begin{align*} w \in L \\ |w| \geq p \\ \end{align*}$

Consider the string $w = (1)^p11(010)^p$ .

$\begin{align*} \#_{111}w = \#_{010}w = p \implies w \in L \\ |w| = 4p + 2 \geq p \\ \end{align*}$

Stating the Pumping Lemma

According to the Pumping Lemma for Regular languages, $w$ can be written as $w = xyz$ , satisfying the following conditions

$\begin{align*} \vert xy \vert & \leq p \\ \vert y \vert & \geq 1 \\ xy^iz & \in L \quad \forall i \geq 0 \end{align*}$

Case 1: $|xy| \leq p$

As $|xy| \leq p$ , $xy$ will be composed entirely of ones. Without loss of generality

$\begin{align*} xy & = (1)^t \quad \quad \quad \quad \quad \quad 1 \leq t \leq p \\ z & = (1)^{p-t}11(010)^p \\ \end{align*}$

Case 2: $|y| \geq 1$

As $|y| \geq 1$ , $y$ must contain at least one $1$ . Without loss of generality

$\begin{align*} y & = (1)^a \quad \quad \quad \quad \quad \quad \quad \quad 1 \leq a \leq p \\ x & = (1)^b \quad \quad \quad \quad \quad \quad \quad \quad 0 \leq b \leq p-a \\ z & = (1)^{p-(a+b)}11(010)^p \\ \end{align*}$

Case 3: $xy^iz \in L \forall i \geq 0$

$\begin{align*} xy^iz & = (1)^b((1)^a)^i(1)^{p-a-b}11(010)^p \\ & = (1)^{b+ai+p-a-b}11(010)^p \\ & = (1)^{p+(i-1)a}11(010)^p \\ \end{align*}$

For $xy^iz \in L$ to hold true

$\begin{align*} \#_{111}xy^iz = p+(i-1)a & = \#_{010}xy^iz = p \\ p+(i-1)a & = p \\ (i-1)a & = 0 \\ \end{align*}$

This will hold true $\forall i \geq 0$ , if $a =0$ . But according to Case 2, $a \geq 1$ . This is a contradiction and all possible cases of expressing $xyz$ have been considered.

Contradiction

The Pumping Lemma does not hold true. This means the assumption that $L$ is Regular was wrong. Thus, $L$ is not Regular.

The Beard Sage