Course contentsShow
← Computer Science
Lesson 1826 of 2,87241. Context-Free LanguagesFree lesson

CFG Closure Properties

Explore how context-free languages are closed under union, concatenation, and Kleene star.

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:

  1. Union: If L₁ and L₂ are context-free, so is L₁ ∪ L₂
  2. Concatenation: If L₁ and L₂ are context-free, so is L₁L₂
  3. 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.