Closure Properties of Regular Languages

In our last lesson, we explored the Pumping Lemma, a powerful tool for proving that a language is not regular by exposing the limitations of finite memory. This lesson tackles the other side of the coin: how can we build complex regular languages from simpler ones?

Today, we will investigate the closure properties of regular languages. The term "closure" in a mathematical context means that when you apply an operation to members of a set, the result is still a member of that set. We will prove that the class of regular languages is closed under the operations of union, concatenation, Kleene star, intersection, and complement. This will not only deepen your understanding of the structure of regular languages but also give you a new set of powerful, high-level tools for reasoning about them.

1. What is a Closure Property?

Before diving into proofs, let's formalize what we mean. A class of languages (in our case, the regular languages) is said to be closed under an operation if, whenever the operation is applied to languages in the class, the result is also a language in that class.

For example, to say regular languages are closed under union means that if $L_{1}$ and $L_{2}$ are regular languages, then the language $L_{1} \cup L_{2}$ is also guaranteed to be regular.

To prove these properties, we have two main strategies, both of which you've encountered:

Construction via Regular Expressions: If we can show that a regular expression for the new language can be built from the regular expressions of the original languages, we're done.
Construction via Automata: If we can show that a finite automaton for the new language can be built from the automata of the original languages, we're also done.

We'll use both strategies, as each provides a different and valuable perspective.

2. Closure under Regular Operations (Union, Concatenation, Star)

Let's begin with the three operations that form the very definition of regular expressions.

An Abstract Proof using Regular Expressions

Given your preference for abstract-first reasoning, there is a remarkably straightforward proof for these three operations. Since any regular language can be described by a regular expression, we can prove closure by simply constructing new regular expressions.

[PDF] Lecture 8 – Closure Properties of Regular Languages - COSE215

These lecture notes from Korea University provide a concise and formal proof based on the definition of regular expressions.

Please read the section titled "Closure under Union, Concatenation, and Kleene Star". The argument is direct: if L_1 and L_2 are regular, they have corresponding regular expressions R_1 and R_2. The expressions R_1|R_2, R_1R_2, and R_1^* are, by definition, also regular expressions. Therefore, the resulting languages are regular.

While this proof is elegantly simple and complete, the proofs by automata construction are more mechanically insightful and demonstrate the power of non-determinism, a concept we've previously established is equivalent in power to determinism.

Constructive Proofs using Non-determinism

In a previous lesson, we established that every NFA has an equivalent DFA. This allows us to freely use NFAs—particularly with $ϵ$ -transitions—to construct machines, knowing that they still define regular languages. The following video from MIT OpenCourseWare brilliantly demonstrates how non-determinism makes these constructions intuitive.

2. Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA

In this video, Prof. Michael Sipser (author of a standard textbook on this subject) explains how to combine automata to prove closure properties.

Watch the following segments to see the constructions for each operation: Union: Union construction. The key idea is to create a new start state that non-deterministically branches to the start states of the two original machines. The machine accepts if either branch accepts. Concatenation: Concatenation construction. Here, we connect the accept states of the first machine to the start state of the second using \epsilon-transitions. Non-determinism elegantly solves the problem of guessing where the first string ends and the second begins. Kleene Star: Star construction. This involves adding \epsilon-transitions from the accept states back to the start state to allow for repetition, and a new start/accept state to handle the empty string.

These constructions beautifully illustrate the "magical guessing" power of NFAs and are fundamental techniques in automata theory.

3. Closure under Complement

What about the strings that are not in a regular language $L$ ? The set of these strings is the complement of $L$ , denoted $L ˉ = Σ^{*} ∖ L$ . Is $L ˉ$ also regular?

The answer is yes, and the proof involves a simple but clever modification to a DFA.

Proof for Complement:

Start with a regular language $L$ . Since $L$ is regular, there must exist a DFA, $D = (Q, Σ, δ, q_{0}, F)$ , that recognizes it.
Construct a new DFA, $D^{'}$ , by simply swapping the final and non-final states of $D$ . The new set of final states is $F^{'} = Q ∖ F$ . All other components remain the same.
Now, for any string $w$ , if the computation of $w$ in $D$ ends in a state in $F$ , then the computation of $w$ in $D^{'}$ ends in a state that is not in $F^{'}$ . So, if $D$ accepts $w$ , $D^{'}$ rejects it.
Conversely, if the computation of $w$ in $D$ ends in a non-final state, that same state is a final state in $D^{'}$ . So, if $D$ rejects $w$ , $D^{'}$ accepts it.
Therefore, $D^{'}$ accepts exactly the strings that $D$ rejects, meaning $L (D^{'}) = L ˉ$ . Since we have constructed a DFA for $L ˉ$ , it is a regular language.

Caption: This diagram illustrates the proof for closure under complement. A DFA M for language L is transformed into a DFA M' for the complement of L by making all of M's accepting states non-accepting and all non-accepting states accepting.

A crucial point for critical thinking: Why does this state-swapping proof only work for DFAs and not for NFAs?

Think about it, then check the answer.

For a DFA, every string ends in exactly one state. That state is either final or not. For an NFA, a string can have multiple computation paths. It is accepted if *at least one* path ends in a final state. If we simply flip the final and non-final states, a string might have paths ending in both new final states and new non-final states. This would mean the new NFA both accepts and rejects the string, which doesn't correctly define the complement. To take the complement of a language recognized by an NFA, you must first convert it to an equivalent DFA (using the subset construction) and *then* flip the states.

4. Closure under Intersection

Now, let's consider the intersection of two regular languages, $L_{1} \cap L_{2}$ . This is the set of strings that are in both $L_{1}$ and $L_{2}$ .

An Abstract Proof using De Morgan's Laws

Your background in logic and mathematics will appreciate this elegant proof. De Morgan's laws state that the intersection of two sets can be expressed using union and complement:
$L_{1} \cap L_{2} = L_{1} \cup L_{2}$
Let's analyze this expression:

If $L_{1}$ and $L_{2}$ are regular, then we've just proven that their complements, $L_{1}$ and $L_{2}$ , are also regular.
We've also shown that the union of two regular languages is regular, so $L_{1} \cup L_{2}$ must be regular.
Finally, the complement of that language must also be regular.

Since we can obtain $L_{1} \cap L_{2}$ from $L_{1}$ and $L_{2}$ using only operations under which regular languages are closed, the result must be regular. This is a powerful demonstration of how closure properties can be used to build arguments.

A Constructive Proof: The Product Construction

While the De Morgan's proof is elegant, it's also useful to have a direct, constructive method. The product construction builds a single DFA that simulates two original DFAs in parallel.

The core idea is to create a new machine whose states are pairs of states, one from each of the original DFAs. A state (p, q) in the new machine represents the fact that the first DFA is in state p and the second is in state q.

The following video walks through a concrete example of this construction.

Regular Languages Closed Under Union/Intersection (Product Construction)

This "Easy Theory" video provides an excellent, step-by-step walkthrough of the product construction for intersection (though it first uses it for union, the principle is the same).

Please watch the following segments: Example setup: The video defines two simple regular languages and their corresponding DFAs, which will be used for the construction. The construction: Observe how the new DFA is built. Its states are the Cartesian product of the original state sets. A transition from (p, q) on symbol a goes to (p', q') where p' is the state p would go to, and q' is the state q would go to. Defining final states: This is the crucial part that defines the operation. For intersection, the new machine should accept only if both original machines accept. Therefore, a state (p, q) is a final state in the product machine if and only if p is a final state in the first machine AND q is a final state in the second. (The video uses this logic to define final states for union, where only one needs to be final. The adaptation for intersection is direct.)

Caption: An example of the product construction for intersection. The DFA on the right has states that are pairs of states from the two DFAs on the left. A string is accepted if and only if it leads to a state `(pi, qj)` where `pi` is an accepting state in the top-left DFA and `qj` is an accepting state in the bottom-left DFA.

Conclusion

In this lesson, you have learned what closure properties are and have seen formal proofs that the class of regular languages is closed under five fundamental set operations.

Key Takeaways:

Definition of Closure: A class of languages is closed under an operation if applying that operation to languages in the class always produces a language that is also in the class.
Regular Languages are Closed Under:
- Union, Concatenation, Kleene Star: Provable abstractly via regular expressions or constructively with NFAs.
- Complement: Provable by swapping final and non-final states in a DFA.
- Intersection: Provable abstractly using De Morgan's laws or constructively with the product automaton.
Proof Techniques: You now have a versatile toolkit for reasoning about regular languages, including direct construction (regex, NFA, DFA) and logical arguments based on other known properties.

These properties are not just theoretical exercises. They form the basis of many algorithms that manipulate regular expressions and automata. In our next lesson, we will see exactly how these concepts are put to use in real-world applications like the lexical analysis phase of a compiler and in the powerful text-search utilities you use every day.

Recommended resources