Closure Properties of Regular Languages

1. Closure Under Complement, Union, and Intersection

We'll begin with three operations that can be proven using a clever, deterministic construction on DFAs. The core idea is to build a new machine that simulates two (or more) DFAs in parallel.

Closure Under Complement

The complement of a language $L$ over an alphabet $\Sigma$, denoted $\bar{L}$, is the set of all strings in ${\Sigma }^{\ast }$ that are not in $L$.
$\bar{L}={\Sigma }^{\ast }-L$
If $L$ is regular, is $\bar{L}$ also regular? Yes, and the construction is surprisingly simple.

Construction:

1. Start with a DFA $M$ that accepts $L$.
2. Crucially, ensure $M$ is complete: for every state, there must be an outgoing transition for every symbol in the alphabet. If not, add a non-final "trap state" and direct all missing transitions there.
3. Create a new DFA, $M^{\prime }$, which is identical to $M$ except that you swap the final and non-final states. Every state that was an accepting state in $M$ is now a non-accepting state in $M^{\prime }$, and vice-versa.

This new machine $M^{\prime }$ accepts a string $w$ if and only if the original machine $M$ did not end in a final state after processing $w$. Therefore, $M^{\prime }$ accepts $\bar{L}$, proving that the class of regular languages is closed under complementation.

Closure Under Union and Intersection (The Product Construction)

To prove closure under union ($L_1\cup L_2$) and intersection ($L_1\cap L_2$), we use a powerful technique called the product construction (or cross-product).

The intuition is to build a single DFA that runs two DFAs, $M_1$ and $M_2$, simultaneously on the same input string. To do this, the state of our new machine will be a pair of states $(p,q)$, where $p$ is the current state of $M_1$ and $q$ is the current state of $M_2$. This is conceptually similar to running two concurrent processes and tracking the state of both.

The following video provides an excellent, step-by-step walkthrough of building a product automaton from scratch for the union of two example languages.

Let's formalize the construction seen in the video. Given two DFAs, $M_1=(Q_1,\Sigma ,{\delta }_1,q_{0,1},F_1)$ for language $L_1$ and $M_2=(Q_2,\Sigma ,{\delta }_2,q_{0,2},F_2)$ for $L_2$, we construct a new DFA $M^{\prime }=(Q^{\prime },\Sigma ,{\delta }^{\prime },q_0^{\prime },F^{\prime })$:

• States $Q^{\prime }$: The Cartesian product of the original state sets: $Q^{\prime }=Q_1\times Q_2$. Each state is a pair $(p,q)$ where $p\in Q_1$ and $q\in Q_2$.
• Start State $q_0^{\prime }$: The pair of the original start states: $q_0^{\prime }=(q_{0,1},q_{0,2})$.
• Transition Function ${\delta }^{\prime }$: On reading symbol $a$ from state $(p,q)$, the new machine transitions to the pair of states that the original machines would have transitioned to:
  ${\delta }^{\prime }((p,q),a)=({\delta }_1(p,a),{\delta }_2(q,a))$
• Final States $F^{\prime }$: This is where union and intersection differ.
  • For Intersection ($L_1\cap L_2$): The new machine accepts if both original machines accept. So, a state $(p,q)$ is final if $p\in F_1$ and $q\in F_2$.
    $F_{intersect}^{\prime }=F_1\times F_2$
  • For Union ($L_1\cup L_2$): The new machine accepts if either of the original machines accepts. So, a state $(p,q)$ is final if $p\in F_1$ or $q\in F_2$.
    $F_{union}^{\prime }=(F_1\times Q_2)\cup (Q_1\times F_2)$

Since we can construct a DFA for both the union and intersection, the class of regular languages is closed under these operations.

2. Closure Under Concatenation and Kleene Star

While the product construction is elegant for DFAs, it doesn't easily extend to concatenation and Kleene star. The problem is that a DFA must decide where one string ends and the next begins, but it has no way to "look ahead." This requires a form of guessing, which is precisely the power that Nondeterministic Finite Automata (NFAs) provide. Using NFAs with $ϵ$-transitions makes these proofs remarkably intuitive.

The following video shows how the challenge of proving closure for concatenation motivates the use of nondeterminism and then demonstrates the simple, elegant constructions for union, concatenation, and Kleene star using NFAs.

Let's summarize these powerful NFA-based constructions.

Union ($L_1\cup L_2$)

Given two NFAs, $M_1$ and $M_2$, create a new NFA $M^{\prime }$ by:

1. Creating a new start state.
2. Adding $ϵ$-transitions from the new start state to the original start states of $M_1$ and $M_2$.
   The machine nondeterministically "chooses" which path to follow. If either path leads to acceptance, the whole machine accepts.

Concatenation ($L_1{L}_2$)

Given $M_1$ and $M_2$, create a new NFA $M^{\prime }$ where:

1. The start state of $M^{\prime }$ is the start state of $M_1$.
2. The final states of $M^{\prime }$ are the final states of $M_2$.
3. Add $ϵ$-transitions from every final state of $M_1$ to the start state of $M_2$.
   When the machine reaches a final state in $M_1$, it can nondeterministically jump to the start of $M_2$ to process the rest of the string.

Kleene Star ($L_1^{\ast }$)

Given an NFA $M_1$, create a new NFA $M^{\prime }$ by:

1. Creating a new start state that is also a final state (to accept $ϵ$).
2. Adding an $ϵ$-transition from the new start state to the original start state of $M_1$.
3. Adding $ϵ$-transitions from every original final state of $M_1$ back to the original start state of $M_1$. This creates the "zero or more" repetition loop.

The image below provides a clean visual summary of these three NFA constructions.

Since we can construct an NFA for each of these operations, and we know from a previous lesson that every NFA can be converted to an equivalent DFA, we have proven that the class of regular languages is also closed under union, concatenation, and Kleene star.

Conclusion

Today, we established the remarkable robustness of the class of regular languages. They are a self-contained family, closed under all the fundamental operations of set theory and string manipulation.

Key Takeaways:

• Closure Property: A class of languages is closed under an operation if applying that operation to languages in the class produces a language that is also in the class.
• Regular Languages are Closed Under:
  • Union, Intersection, Complement: These can be proven using the product construction on DFAs, which simulates two machines in parallel. The definition of final states determines the specific operation.
  • Concatenation and Kleene Star: These are proven most easily using NFA constructions with $ϵ$-transitions. Nondeterminism elegantly solves the problem of guessing where one part of a string ends and another begins.

Preview of the Next Lesson:
Our closure constructions, particularly the product construction and NFA-to-DFA conversion, can result in automata with a very large number of states. This raises a practical question: is this the smallest machine possible? In the next lesson, we will address this by learning how to minimize DFAs. We will learn an algorithm to find and merge indistinguishable states, resulting in a unique minimal DFA for any given regular language.