Closure Properties of CFLs: Union, Concatenation, and Kleene Star

Hello! Welcome back to our study of the Theory of Computation.

In our last lesson, we developed a powerful tool, the Pumping Lemma for Context-Free Languages, and used it to prove that certain languages, like {aⁿbⁿcⁿ | n ≥ 0}, are not context-free. Today, we'll explore the other side of the coin: which operations can you perform on CFLs that are guaranteed to result in another CFL? This is the study of closure properties.

Our goal for this lesson is to prove that Context-Free Languages are closed under the regular operations: union, concatenation, and Kleene star. We will do this by using grammar-based constructions, which means we will learn how to take the grammars of existing CFLs and systematically combine them to build a new grammar for the resulting language.

Why Grammars?

For these proofs, we have a choice between our two equivalent models for CFLs: Pushdown Automata (PDAs) and Context-Free Grammars (CFGs). While it's possible to prove closure by combining PDAs, it's often much more complex. Stitching grammars together, on the other hand, is surprisingly elegant and intuitive. Your experience in software development, where you combine different modules or components to build a larger system, will provide a helpful parallel for what we're about to do.

To get a high-level overview of the constructions we'll be discussing, please start by watching the first part of this video.

Closure Properties of Context-Free Languages

This video from Easy Theory provides a clear and intuitive introduction to the closure properties of CFLs. It explains why we use grammars and walks through the core ideas behind the constructions for union, concatenation, and Kleene star.

Please watch from the beginning until 09:00. Focus on the main strategy for each of the three operations (Union, Concatenation, Star) and the new rules that are introduced.

Now that you have the main ideas, let's formalize them and prove each property one by one.

The Setup

For the proofs of union and concatenation, let's assume we have two context-free languages, $L_{1}$ and $L_{2}$ . Since they are CFLs, they must be generated by some CFGs, say $G_{1}$ and $G_{2}$ .

$G_{1} = (V_{1}, Σ_{1}, R_{1}, S_{1})$ where $L (G_{1}) = L_{1}$ .
$G_{2} = (V_{2}, Σ_{2}, R_{2}, S_{2})$ where $L (G_{2}) = L_{2}$ .

A crucial first step in combining these grammars is to ensure they don't interfere with each other. Specifically, their sets of variables must be disjoint ( $V_{1} \cap V_{2} = \emptyset$ ). If they aren't, we can simply rename the variables in one of the grammars (e.g., change every variable X in $G_{2}$ to X'). This is analogous to avoiding namespace collisions in programming. We will assume this has been done for all the constructions below.

1. Closure Under Union

Claim: If $L_{1}$ and $L_{2}$ are CFLs, then $L_{1} \cup L_{2}$ is also a CFL.

Construction: We will build a new grammar $G_{u ni o n}$ that generates any string from $L_{1}$ or any string from $L_{2}$ . The idea is to create a new start symbol that acts as a switch, choosing to proceed with either the grammar for $L_{1}$ or the grammar for $L_{2}$ .

Let $G_{u ni o n} = (V, Σ, R, S)$ , where:

Variables $V$ : $V_{1} \cup V_{2} \cup {S}$ , where $S$ is a brand new start symbol not in $V_{1}$ or $V_{2}$ .
Alphabet $Σ$ : $Σ_{1} \cup Σ_{2}$ .
Start Symbol: $S$ .
Rules $R$ : $R_{1} \cup R_{2} \cup {S \to S_{1} ∣ S_{2}}$ . We take all the rules from both original grammars and add two new rules from our new start symbol.

Why it works: A derivation in $G_{u ni o n}$ must start with $S$ . The very first step must be either $S \Rightarrow S_{1}$ or $S \Rightarrow S_{2}$ .

If we choose $S \Rightarrow S_{1}$ , the rest of the derivation can only use rules from $G_{1}$ (since the variable sets are disjoint). Therefore, we will generate a string in $L_{1}$ .
If we choose $S \Rightarrow S_{2}$ , the rest of the derivation can only use rules from $G_{2}$ , generating a string in $L_{2}$ .

Since any derivable string must belong to either $L_{1}$ or $L_{2}$ , the language of $G_{u ni o n}$ is exactly $L_{1} \cup L_{2}$ .

Closure Properties of Context-Free Languages: Union Proof Start — This image provides a concise visual summary of the theorem and the grammar-based construction for proving closure under union.

2. Closure Under Concatenation

Claim: If $L_{1}$ and $L_{2}$ are CFLs, then their concatenation $L_{1} \cdot L_{2}$ is also a CFL.

Construction: We'll build a new grammar $G_{co n c a t}$ where the start symbol generates the start symbol of $G_{1}$ followed by the start symbol of $G_{2}$ .

Let $G_{co n c a t} = (V, Σ, R, S)$ , where:

Variables $V$ : $V_{1} \cup V_{2} \cup {S}$ , where $S$ is a new start symbol.
Alphabet $Σ$ : $Σ_{1} \cup Σ_{2}$ .
Start Symbol: $S$ .
Rules $R$ : $R_{1} \cup R_{2} \cup {S \to S_{1} S_{2}}$ .

Why it works: Any derivation must start with $S \Rightarrow S_{1} S_{2}$ . Because the variable sets are disjoint, the part of the derivation that starts from $S_{1}$ can only produce a string from $L_{1}$ , let's call it $w_{1}$ . Similarly, the part starting from $S_{2}$ can only produce a string from $L_{2}$ , call it $w_{2}$ . The final string will be $w_{1} w_{2}$ , which is precisely the definition of a string in the language $L_{1} \cdot L_{2}$ .

3. Closure Under Kleene Star

Claim: If $L_{1}$ is a CFL, then $L_{1}^{*}$ is also a CFL.

Construction: For the Kleene star, we need to generate zero or more concatenations of strings from $L_{1}$ . This suggests a recursive definition. Our new grammar, $G_{s t a r}$ , will have a start symbol that can either stop (producing the empty string $ϵ$ ) or generate one string from $L_{1}$ and then recursively call itself to generate the rest.

Let $G_{s t a r} = (V, Σ, R, S)$ , where:

Variables $V$ : $V_{1} \cup {S}$ , where $S$ is a new start symbol.
Alphabet $Σ$ : $Σ_{1}$ .
Start Symbol: $S$ .
Rules $R$ : $R_{1} \cup {S \to S S_{1} ∣ ϵ}$ .

Why it works:

To generate the empty string (which is always in $L_{1}^{*}$ ), we use the rule $S \to ϵ$ .
To generate a non-empty string like $w_{1} w_{2} ... w_{k}$ (where each $w_{i} \in L_{1}$ ), we can use the rule $S \to S S_{1}$ $k$ times, resulting in a sentential form like $S S_{1} S_{1} ... S_{1}$ . We then use $S \to ϵ$ to terminate the recursion, leaving $S_{1} S_{1} ... S_{1}$ . Each $S_{1}$ can then derive a string from $L_{1}$ , giving us the desired concatenation.

To solidify your understanding and see these constructions presented with formal proofs, please read the following document.

Lecture 10 - Closure Properties for Context-Free Languages

These lecture notes from the University of Waterloo provide a rigorous, formal proof for each of the three closure properties. It's an excellent resource for understanding the precise logic behind why these constructions work.

Please read section 10.1, "The regular operations" (pages 1-2). For each operation (Union, Concatenation, Star), focus on the formal construction of the new grammar and the two-part argument that proves L(G) is the desired language.

Test your understanding!

Let's say you have two grammars:

$G_{1}$ with start symbol $S_{1}$ for the language $L_{1} = {a^{n} b^{n} ∣ n \geq 0}$ . Its rules are $S_{1} \to a S_{1} b ∣ ϵ$ .
$G_{2}$ with start symbol $S_{2}$ for the language $L_{2} = {c^{m} ∣ m \geq 1}$ . Its rules are $S_{2} \to c S_{2} ∣ c$ .

Construct the set of rules for a new grammar $G_{co n c a t}$ that generates the language $L_{1} \cdot L_{2}$ . What is one example of a string (not in $L_{1}$ or $L_{2}$ ) that your new grammar can generate?

Show answer

The new grammar $G_{co n c a t}$ will have a new start symbol, let's call it $S$ . We combine the rules from $G_{1}$ and $G_{2}$ and add one new rule for $S$ .

The full set of rules for $G_{co n c a t}$ would be:

$S \to S_{1} S_{2}$ (The new rule)
$S_{1} \to a S_{1} b$ (From $G_{1}$ )
$S_{1} \to ϵ$ (From $G_{1}$ )
$S_{2} \to c S_{2}$ (From $G_{2}$ )
$S_{2} \to c$ (From $G_{2}$ )

An example of a string generated could be aabbcc.
Here's the derivation:
$S \Rightarrow S_{1} S_{2}$
$\Rightarrow a S_{1} b S_{2}$ (using $S_{1} \to a S_{1} b$ )
$\Rightarrow aa S_{1} bb S_{2}$ (using $S_{1} \to a S_{1} b$ again)
$\Rightarrow aabb S_{2}$ (using $S_{1} \to ϵ$ )
$\Rightarrow aabb c S_{2}$ (using $S_{2} \to c S_{2}$ )
$\Rightarrow aabb cc$ (using $S_{2} \to c$ )

Conclusion

In this lesson, we have formally proven that the set of context-free languages is closed under union, concatenation, and Kleene star.

Key Takeaways:

Closure means that applying an operation to languages within a class produces a language that is also in that class.
We can prove these closure properties for CFLs using constructive proofs based on grammars.
Union: Create a new start symbol $S$ with rules $S \to S_{1} ∣ S_{2}$ .
Concatenation: Create a new start symbol $S$ with the rule $S \to S_{1} S_{2}$ .
Kleene Star: Create a new start symbol $S$ with recursive rules $S \to S S_{1} ∣ ϵ$ .
A critical prerequisite for these constructions is ensuring the variable sets of the original grammars are disjoint.

Preview of the Next Lesson:
We've seen that CFLs are closed under the same operations as regular languages. But does this hold for all set operations? Consider the languages $L_{1} = {a^{n} b^{n} c^{m} ∣ n, m \geq 0}$ and $L_{2} = {a^{m} b^{n} c^{n} ∣ n, m \geq 0}$ . Both are context-free. What is their intersection, $L_{1} \cap L_{2}$ ? It's {aⁿbⁿcⁿ | n ≥ 0}, which we proved in our last lesson is not a CFL! This strongly suggests that CFLs are not closed under intersection. In the next lesson, we will formalize this and also investigate closure under complement.

Recommended resources