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

Closure Properties: Star and Complement

Regular languages are closed under Kleene star and complement, using NFA and DFA transformations.

Closure Properties: Star and Complement

What You'll Learn

You'll discover how to prove that regular languages remain regular when you apply the Kleene star operator or take their complement—two fundamental closure properties.

The Core Idea

A closure property means that applying certain operations to regular languages always produces another regular language. You've already seen union and concatenation; now we tackle star and complement.

Closure Under Star (Kleene Star)

If L is a regular language, then L* (zero or more repetitions of strings from L) is also regular.

Proof sketch: Given an NFA for L, we construct a new NFA for L* by:

  1. Adding a new start state that is also accepting (handles the empty string in L*)
  2. Adding epsilon transitions from all old accepting states back to the old start state (enables repetition)

This NFA construction directly proves closure—NFAs naturally handle the "guess where to restart" logic needed for star.

Closure Under Complement

If L is a regular language over alphabet Σ, then its complement L̄ (all strings in Σ* that are not in L) is also regular.

Proof sketch: Given a DFA for L:

  1. Take the same DFA structure
  2. Swap accepting and non-accepting states

This works because DFAs are deterministic—every string has exactly one path, so flipping acceptance perfectly inverts the language. (Note: this proof requires a DFA, not an NFA, because NFAs can have multiple paths.)

Why It Matters

These closure properties give you powerful tools for building complex languages from simpler ones and for reasoning about what regular languages can express.

Key Takeaway: Regular languages are closed under Kleene star (proven by NFA construction) and complement (proven by swapping accepting states in a DFA).