Using Closure Properties to Show Nonregularity

Proving languages are not regular using closure properties

Using our knowledge of a few nonregular languages, we can conclude that other languages are nonregular merely by using the closure properties of regular languages. For example, the language NOTPRIME ($\{a^n\}$ where $n$ is not prime) is not regular. If it were, then its complement, PRIME ($\{a^n\}$ where $n$ is prime), would also be, but we know that PRIME is not regular, so NOTPRIME can’t be regular since regular languages are closed under complement.

It is fruitless to attempt to use the pumping theorem on a language like this, defined with a negative (e.g., using “not”). Instead, we show its complement is not regular. Depending on the language, other closure properties can be used to show that a language is not regular.

We can also show that the language EQUAL, defined as $\{n_a(w)=n_b(w)\;|\;w \in (a+b)^*\}$ (i.e., strings where the number of $a$’s and $b$’s are equal, but the letters can appear in any order), is not regular by applying the pumping theorem to the string $a^pb^p$ (remember, we can choose any qualifying string in the language). But we can use the closure properties of regular languages to avoid having to use the pumping theorem. Consider the set of strings formed by the intersection EQUAL $\cap \; a^*b^*$. This is the set of strings of $a$’s and $b$’s where the number of each letter is equal, but also where the $a$’s must precede the $b$’s. But this is also the language $L_{ab}=a^nb^n$, which we already know is not regular. Since $a^*b^*$ represents a regular language, then EQUAL must not be regular because regular languages are closed under intersection.

The language $L_{ne}=\{a^m b^n \;|\; m \neq n\}$ is not regular (notice the $\neq$, which implies a “not”). Since we don’t get to choose the size of $y$, it is possible that pumping $y$ will leave the number of $a$’s unequal to the number of $b$’s. In general, we can’t prove a negative with any theorem directly. This language is not the complement of $L_{ab}=\{a^nb^n\}$, by the way, because $\overline{L_{ab}}$ also includes strings that aren’t necessarily a run of $a$’s followed by a run of $b$’s, no matter the number of occurrences of each character (strings like $bbaa$, as well as strings like $baa$, and $abab$). However, $L_{ne}$ does include all the strings in $\overline{L_{ab}}$, which are run of $a$’s followed by a run of $b$’s, so we can compute the following difference: