Closure Properties of (the set of) Regular Languages

By definition, the union of two regular languages is regular, the concatenation of two regular languages is regular, and the star of a regular language is regular. In this section we look at other operations on regular languages that are guaranteed to produce regular languages. Specifically:

The complement of a regular language is regular.
The intersection of two regular languages is regular.

Theorems of this kind are called closure properties, because they tell us that the collection of all regular languages is closed under particular operations. (A set is closed under an operation if applying that operation to members of the set is guaranteed to produce members of that same set.)

Closure under Complement

Theorem

The complement of a regular language is regular.

Proof:
Let $S$ be an arbitrary regular language. There exists a DFA $D$ such that $S = L(D)$ . Define $D'$ to be a DFA just like $D$ but with accept/reject swapped (i.e., the set $F$ of final/accepting states is replaced by $Q \setminus F$ ). Then $D'$ accepts a string iff $D$ rejects that string. That is, $L(D') = L(D)^C = S^C$ , so the complement $S^C$ of $S$ is regular too.

Example

The complement of the set $\{\ ab^nc\ |\ n\geq 0\ \}$ is regular, because we can find a DFA for this set:

DFA for ab*c

and use that to construct the DFA for the complement:

DFA for strings not in ab*c

Closure Under Intersection

Theorem

The intersection of two regular languages is regular.

Proof 1:
Let $L_1$ and $L_2$ be arbitrary regular languages. Since $(L_1\cap L_2)^c= L_1^c\cup L_2^c$ (a form of DeMorgan’s Law), it follows that $L_1\cap L_2 = (L_1^c\cup L_2^c)^c$ . We know $L_1^c$ and $L_2^c$ are regular. So $L_1^c\cup L_2^c$ is regular Thus $L_1\cap L_2 = (L_1^c∪ L_2^cc)^c$ is regular.

Theorem

The intersection of two regular languages is regular.

Proof 2:
Given DFAs $D_1=(Q_1,\Sigma, \delta_1, q_{01}, F_1)$ and $D_2=(Q_2,\Sigma, \delta_2, q_{02}, F_2)$ accepting the two regular languages, we can construct a new DFA $D=(Q,\Sigma,\delta,q_0,F)$ , called the Product Automaton of $D_1$ and $D_2$ that accepts inputs and keeps track of what states $D_1$ and $D_2$ would be in when given those inputs (i.e., we are simulating the two machines being run in parallel), and only accept if both machines would accept the input string.

Formally, we can define the components of the product automaton as follows:

$Q := Q_1\times Q_2$
The states of $D$ are pairs telling us where $D_1$ and $D_2$ would be on the input so far.
$q_0 := \langle q_{01}, q_{02} \rangle$
When we start, both machines are in their start states
$\delta(\langle q_1,q_2 \rangle, a) := \langle\delta_1(q_1,a), \delta_2(q_2,a)\rangle$
If the first machine is in state $q_1$ and the second machine is in state $q_2$ and we see input $a$ , we use the transition functions of the machines to figure out which states the two machines will be in afterwards.
$F := F_1 \times F_2$
We have found a string in the intersection iff both machines have reached an accepting state.

Example

Here are two small DFAs and their product automaton:

Two small DFAs

Their Product Automaton

Initially the first DFA is in state A and the second DFA is in state L. If the first input is a, then the first DFA switches to state X and the second machine switches to state K. Conversely, if the first input is b, then the first DFA stays in state A, but the second DFA switches to state K. And so on…