Course contentsShow
← Computer Science
Lesson 1803 of 2,87240. Theory of Computation: Regular LanguagesFree lesson

Closure Properties: Union and Concatenation

Regular languages are closed under union and concatenation operations, proven via automata construction.

Closure Properties: Union and Concatenation

You'll learn: How regular languages remain regular when combined using union or concatenation operations.

What Does "Closed Under" Mean?

When we say a class of languages is closed under an operation, we mean applying that operation to languages in the class always produces another language in the same class. Think of it like addition with whole numbers: adding two whole numbers always gives you another whole number—whole numbers are "closed under addition."

Union Closure

Union means combining two languages: L₁ ∪ L₂ contains all strings from either language.

If you have two regular languages (each recognized by some DFA or NFA), their union is also regular. Proof strategy: Build an NFA that runs both original NFAs "in parallel" using nondeterminism. At the start state, use epsilon transitions to nondeterministically choose which NFA to simulate. If either NFA accepts, your combined NFA accepts.

Alternatively, using DFAs, you can use the product construction you've seen before: create states for every pair (q₁, q₂) and accept when either component would accept.

Concatenation Closure

Concatenation L₁ · L₂ contains strings formed by taking any string from L₁ followed by any string from L₂.

Regular languages are closed under concatenation too. Proof strategy: Build an NFA that first simulates the NFA for L₁, then uses epsilon transitions from L₁'s accepting states to "jump" to the start of L₂'s NFA. This chains the two recognizers together.

Why This Matters

These closure properties guarantee you can build complex regular languages from simpler ones without leaving the class of regular languages. This makes regular languages a robust, composable foundation for pattern matching and lexical analysis.

Key Takeaway: Regular languages are provably closed under union and concatenation—combining regular languages with these operations always yields another regular language, proven via automata construction techniques.