Using Closure Properties to Show Nonregularity

Learn how to use closure properties to show that a language is not regular.

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 ({an}\{a^n\} where nn is not prime) is not regular. If it were, then its complement, PRIME ({an}\{a^n\} where nn 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 {na(w)=nb(w)    w(a+b)}\{n_a(w)=n_b(w)\;|\;w \in (a+b)^*\} (i.e., strings where the number of aa’s and bb’s are equal, but the letters can appear in any order), is not regular by applying the pumping theorem to the string apbpa^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   ab\cap \; a^*b^*. This is the set of strings of aa’s and bb’s where the number of each letter is equal, but also where the aa’s must precede the bb’s. But this is also the language Lab=anbnL_{ab}=a^nb^n, which we already know is not regular. Since aba^*b^* represents a regular language, then EQUAL must not be regular because regular languages are closed under intersection.

The language Lne={ambn    mn}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 yy, it is possible that pumping yy will leave the number of aa’s unequal to the number of bb’s. In general, we can’t prove a negative with any theorem directly. This language is not the complement of Lab={anbn}L_{ab}=\{a^nb^n\}, by the way, because Lab\overline{L_{ab}} also includes strings that aren’t necessarily a run of aa’s followed by a run of bb’s, no matter the number of occurrences of each character (strings like bbaabbaa, as well as strings like baabaa, and abababab). However, LneL_{ne} does include all the strings in Lab\overline{L_{ab}}, which are run of aa’s followed by a run of bb’s, so we can compute the following difference:

Get hands-on with 1200+ tech skills courses.