Closure Properties

We know that the union, concatenation, and Kleene star of regular languages are also regular because they exhibit NFAs that accept them. The term that describes the property of operators “staying within the same class of language” is called closure; just as integers are closed under addition, subtraction, and multiplication, we say that regular languages are closed under union, concatenation, and Kleene star.

Note: A set is closed under an operation if the result of the operation remains in that set.

Now, we’ll take a deeper look at closure and other properties of regular languages, and develop algorithms for making decisions about regular languages. Finally, we’ll introduce formal languages that are not regular.

Reversing a finite automaton

We know that regular languages are closed under complementation by inverting the acceptability of each state in a DFA that accepts a language. Therefore, having found an automaton that accepts the complement of the original language, we conclude that the complement of any regular language is regular.

We can show that reversing the strings in a regular language results in another regular language by “reversing” its machine. To reverse a machine, we do the following:

• Remove any jail state ( because jail states become unreachable when arrows are reversed).
• If there is more than one accepting state, we create a new, unique, accepting state, reachable from what were the accepting states, by lambda transitions.
• We make the original start state the new, unique, accepting state.
• We make the original (now unique) accepting state the new start state.
• We reverse all edges (and their strings if the diagram is a GTG).

Example: Reversing a machine that accepts the language $aa^*c^*b^*$

To illustrate this, we’ll reverse the machine that accepts the language $L=aa^*c^*b^*$.

Since there are multiple accepting states, we begin by creating a unique accepting state with incoming lambda transitions. We also remove the jail.

We now reverse the arrows, as well as the roles of the initial and final state, to obtain the following NFA for the reverse language.

This machine accepts $b^*c^*a^*a$, a regular expression for the reversal of the original language.

Closure properties of regular languages

Since languages are sets, we consider other set operations for closure. It is easy to show that closure under union and complement is sufficient to guarantee closure under intersection and difference with these set identities.

Since regular languages are closed by the operations used on the right-hand sides above, the sets on the left are also regular by construction.

We conclude that the class of regular languages is closed under the following operations:

• Union
• Concatenation
• Kleene star
• Complement
• Reversal
• Intersection
• Set difference
• Set symmetric difference

It is important to understand that arbitrary subsets of regular languages are generally not regular. As a counterexample, the language $\{a^nb^n \;|\; n \ge 0\}$ is a subset of $a^*b^*$. The language $a^*b^*$ ...