CFG Closure Properties
What you'll learn: You'll discover which operations preserve context-free languages—meaning when you combine CFLs in certain ways, the result is still context-free.
The Core Idea
Just as regular languages are closed under certain operations (union, concatenation, star), context-free languages (CFLs) also maintain closure under some—but not all—operations. When we say a language family is "closed" under an operation, we mean: if you start with languages in that family and apply the operation, the result is guaranteed to stay in the same family.
Context-free languages are closed under three key operations:
- Union: If L₁ and L₂ are context-free, so is L₁ ∪ L₂
- Concatenation: If L₁ and L₂ are context-free, so is L₁L₂
- Kleene Star: If L is context-free, so is L*
Why This Works
The beauty is in the grammar construction. Since each CFL has a CFG, we can mechanically build new grammars:
- Union: Create a new start symbol S with productions S → S₁ | S₂, where S₁ and S₂ are the original start symbols.
- Concatenation: Create S → S₁S₂ (first generate a string from L₁, then one from L₂).
- Star: Create S → ε | SS₁ (generate zero or more strings from L).
Analogy: Think of CFGs as recipes. Union lets you choose between two recipes. Concatenation follows one recipe, then another. Star repeats a recipe any number of times. Each still produces a valid "dish" (context-free language).
Key Takeaway:
Context-free languages are closed under union, concatenation, and Kleene star—you can combine CFLs with these operations and always get another CFL.