Proving a Language is not Regular using Closure Properties

Consider the following language definition

$\begin{equation*} L_1 = \{w \in \{0, 1\}^* : w \text{ contains the same number of 0s and 1s}\} \end{equation*}$

The order of $0$ s and $1$ s does not matter. This language is not regular. This article explores a step by step approach to prove this by using closure properties.

Non-Regular Language

Consider another language definition

$\begin{equation*} L_2 = \{w \in \{0, 1\}^* : w \text{ is of the form } 0^n1^n : n \geq 0\} \end{equation*}$

The order of $0$ s and $1$ s does matter. The above language is also not regular. This can be proved using the Pumping Lemma for Regular languages.

Using this information, $L_1$ can be reduced to $L_2$ as shown below

Intersection

Notice the following

$\begin{equation*} L_1 \cap 0^*1^* = L_2 \end{equation*}$

The number of $0$ s and $1$ s in $L_1$ are equal. However, the order of $0$ s and $1$ s does not matter. The intersection of $L_1$ with $0^*1^*$ will generate a language with equal number of $0$ s and $1$ s where all the $0$ s have to come before the $1$ s. This is $L_2$ .

Since $0^*1^*$ is a regular expression, it is regular.

Closure Properties

With the above understanding, the intersection statement can be expressed as

$\begin{equation*} L_1 \cap \text{Regular} = \text{Non-Regular} \end{equation*}$

Regular languages are closed under intersection. If $L_1$ were to be regular then the above statement won’t hold true. Thus, $L_1$ must be non-regular.

The Beard Sage

Proving a Language is not Regular using Closure Properties

Non-Regular Language

Intersection

Closure Properties

Leave a Reply Cancel reply