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.

Operation	Notation	Equivalent Expression
Intersection	$R \cap S$	$\overline{\overline{R} \cup \overline{S}}$
Difference	$R - S$	$R \cap \overline{S}$
Symmetric difference	$R \ominus S$	$(R - S) \cup (S - R)$

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^*$ is regular, but $\{a^nb^n \;|\; n \ge 0\}$ is not regular.

Note: An arbitrary subset of a regular language is not necessarily regular.

Computing set operations

We can compute the union, concatenation, Kleene star, complement, and reversal of regular languages by modifying or combining automata as needed, but how do we construct the intersection of two regular languages? The answer is to track the two machines concurrently and then assign accepting states only where both machines accept simultaneously.

The process is similar to the Rabin-Scott subset construction process and gives us the union, intersection, and differences all at once through a product table. The product table process uses DFAs (not NFAs) and begins with the start states of the two automata as its composite initial state. We simply track where the machines take us simultaneously for each possible input. Since we need to track all possible machine movements, we must start with DFAs.

Examples of product tables

Let’s form the product table for the two automata. The DFA one that accepts strings of even length is given below.

The DFA one that accepts strings ending with $b$ is given below.

To track the two machines simultaneously, we begin with the composite state $\{E,q_0\}$ as the initial state for the product table.

State	$\pmb{a}$	$\pmb{b}$
$\pmb{\{E,q_0\}}$	$\{O,q_0\}$	$\{O,q_1\}$

...