Proving a Language is not Regular using Closure Properties

Consider the following language definition

The order of s and 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

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

Using this information, can be reduced to as shown below

Intersection

Notice the following

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

Since is a regular expression, it is regular.

Closure Properties

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

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