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.


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.


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

1 Comment Proving a Language is not Regular using the Pumping Lemma

  1. Pingback: Visualizing the Pumping Lemma for Regular Languages - TheBeardSage

Leave a Reply

Your email address will not be published. Required fields are marked *