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 0s and 1s 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 0s and 1s 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


Notice the following

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

The number of 0s and 1s in L_1 are equal. However, the order of 0s and 1s does not matter. The intersection of L_1 with 0^*1^* will generate a language with equal number of 0s and 1s where all the 0s have to come before the 1s. 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.

Leave a Reply

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