Closure and decision properties of regular languages
Closure properties say which operations on languages keep regularity; decision properties say which questions about regular languages are algorithmically solvable and how to decide them.
Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.
Why it matters
Regular languages model patterns engineers use in lexical analysis, hardware controllers, protocol message formats and simple pattern matching. Knowing closure properties lets you combine patterns and know the result is still regular (implementable by finite automata); decision properties tell you which questions about these patterns (emptiness, membership, equivalence, inclusion, finiteness, universality) you can algorithmically answer and how.
Key ideas
Start with assumptions and definitions used throughout:
- Alphabet Σ: a finite set of symbols.
- A language is any set of finite-length strings over Σ.
- A deterministic finite automaton (DFA) is a 5-tuple (Q, Σ, δ, q0, F) where Q is finite set of states, δ: Q×Σ → Q is total transition function, q0 ∈ Q is start state, F ⊆ Q is set of accepting states. (Define NFA similarly but δ may give a set of next states and ε-transitions are allowed.)
- A language is regular if some DFA (equivalently NFA or regular expression) accepts exactly that language.
Closure properties: exact statements and typical constructions (assumptions: alphabets are the same Σ unless otherwise noted; when needed convert NFAs to DFAs or complete DFAs):
- Union: If L1 and L2 are regular then L1 ∪ L2 is regular. Typical construction: construct an NFA with a new start state s and ε-transitions to the start states of NFAs for L1 and L2. If working with DFAs, you can instead use the product construction with accepting pairs where at least one component is accepting (logical OR on the components’ accepting status).
- Concatenation: If L1 and L2 are regular then L1·L2 = {xy | x∈L1, y∈L2} is regular. Construction: for NFAs, connect final states of NFA for L1 via ε-transitions to start state of NFA for L2 and make L2's finals the finals of the combined machine.
- Kleene star: If L is regular then L* is regular. Construction: add ε-transitions from new start to old start and from old finals back to old start; make new start final.
- Complement: If L is regular then Σ* \ L is regular. Requirement: use a DFA that is complete (δ defined on every symbol from every state). Complement by swapping accepting and non-accepting states: new F = Q \ F. (If starting from NFA, determinize and make complete first.)
- Intersection: If L1 and L2 are regular then L1 ∩ L2 is regular. Construction: product automaton (Cartesian product) of DFAs: states Q1×Q2, start (q01,q02), transition (p1,p2) on a → (δ1(p1,a), δ2(p2,a)), accepting pairs where both components accept.
- Set difference (L1 \ L2): regular, since L1 \ L2 = L1 ∩ (Σ* \ L2) and complement and intersection preserve regularity.
- Reversal: If L is regular then L^R = {w^R | w ∈ L} is regular. Construction: reverse all transitions in an NFA, swap start and finals (use new start with ε to former finals if many), and make the new final be the old start.
- Homomorphism: If h: Σ → Γ* is a homomorphism and L ⊆ Σ* regular then h(L) is regular. Construction: replace each transition labelled a by a path of transitions labelled by h(a) (or build NFA simulating blocks).
- Inverse homomorphism: If h: Σ → Γ* and L ⊆ Γ* regular then h^{-1}(L) = {w ∈ Σ* | h(w) ∈ L} is regular. Construction: simulate h(w) in automaton for L (standard construction yields DFA/NFA).
- Left and right quotient: For any language A and regular B, both A^{-1}B = {x | ∃y∈A: yx∈B} and BA^{-1} = {x | ∃y∈A: xy∈B} are regular. Construction idea: using the DFA for B, for left quotient make as ε-start states all B-states reachable by some y∈A; for right quotient mark as accepting all B-states from which some y∈A reaches a B-final state.
Decision properties: exact statements and algorithms (assume input is a finite description of an automaton or regular expression):
- Membership (word problem): Given regular language L (by DFA/NFA/regex) and string w, decide if w ∈ L. Decidable: run automaton on w (for NFA use simulation/backtracking or convert to DFA). Time: O(|w|) for DFA using table lookups; for NFA, simulate the set of current states (with ε-closures) in O(|w|·|Q|), or determinize first.
- Emptiness: Given DFA/NFA, decide if L = ∅. Decidable: perform reachability (BFS/DFS) from start state; if no accepting state is reachable, language is empty.
- Finiteness / Infiniteness: Given DFA, decide if L finite. Decidable: if there exists a reachable cycle that can also reach a final state, language is infinite; otherwise finite. (Reason: a DFA with no such cycle accepts only bounded-length paths.)
- Universality: Given DFA, decide if L = Σ*. Decidable: complement and test emptiness of complement: L = Σ* iff Σ* \ L is empty.
- Equivalence: Given two DFAs, decide if they accept same language. Decidable: construct product DFA for symmetric difference L1 △ L2 = (L1 \ L2) ∪ (L2 \ L1) and test emptiness. Alternatively minimize both DFAs (Myhill–Nerode) and check isomorphism.
- Inclusion (L1 ⊆ L2): decidable by testing L1 ∩ (Σ* \ L2) = ∅.
Remarks about assumptions and common exam derivations:
- Many constructions are easiest described with NFAs plus ε-transitions; determinize (subset construction) when a DFA is required (e.g., for complement).
- When complementing, ensure DFA is complete (add dead state) before swapping accepting states.
- For intersection and equivalence the product construction is the canonical derivation universities expect.
Describe diagrams to draw in exams:
- For union via NFA: draw two NFAs side-by-side, a new start state s with ε-arrows to each original start; mark original final states as final. Label ε on those arrows. (If start had ε already, note it.)
- For product DFA: draw a grid of pairs of states (rows states of A, columns states of B), label start as (q0A,q0B) and accepting pairs where both components are accepting.
- For emptiness check: draw DFA and cross out all states unreachable from start; if any final remains, not empty.
Formulas
L1 ∪ L2 — union of languages L1 and L2; applies for any languages; if L1,L2 regular then result is regular.
L1 · L2 — concatenation: {xy | x∈L1, y∈L2}.
L* — Kleene star: union of finite concatenations of L, including ε.
Σ* \ L — complement of L relative to Σ* (all strings over Σ not in L); requires DFA complete before swapping accept/reject.
L1 ∩ L2 — intersection, equals complement(complement(L1) ∪ complement(L2)) (De Morgan).
L1 \ L2 — difference, equals L1 ∩ (Σ* \ L2).
h(L) — homomorphic image of L under h: { h(w) | w∈L }.
h^{-1}(L) — inverse homomorphic image: { w | h(w)∈L }.
For each symbol: L, L1, L2 are languages; Σ is alphabet; h: Σ→Γ* is a homomorphism. These are not SI units; they apply to formal languages.
Worked examples
Example 1 — prove union of two regular languages is regular (model exam answer):
- Given NFAs N1 = (Q1, Σ, δ1, q01, F1) for L1 and N2 = (Q2, Σ, δ2, q02, F2) for L2.
- Construct N = (Q, Σ, δ, q0, F) where Q = Q1 ∪ Q2 ∪ {q0} (q0 new start; assume Q1 and Q2 are made disjoint by renaming if needed), δ extends δ1, δ2 and has δ(q0, ε) = {q01, q02} (two ε-transitions). F = F1 ∪ F2.
- Argument: any string accepted by N must follow either the branch into N1 or N2 and thus belongs to L1 or L2; any x ∈ L1 is accepted by N via ε to q01 and the accepting path in N1. Therefore L(N) = L1 ∪ L2, so union is regular.
- Diagram to draw: new start state with two ε-arrows to starts of the two NFAs.
Example 2 — decide emptiness of a DFA (model exam answer / step-by-step trace): Given DFA D with states {q0,q1,q2,q3}, start q0, accepting {q3}, transitions: q0 -a→ q1, q1 -b→ q2, q2 -a→ q1, q2 -b→ q3, q3 loops to q3 on a,b.
- Run BFS from q0: discover q0, then q1, then q2, then q3.
- Since q3 (accepting) is reachable, L(D) ≠ ∅. Return "not empty" and can produce example string: path q0 -a→ q1 -b→ q2 -b→ q3 corresponds to "abb" accepted.
- This algorithm is O(|Q|+|δ|) time.
Example 3 — test equivalence of two DFAs via product construction (model answer):
- Given DFAs A and B, build product DFA P whose states are pairs (p,q), start (p0,q0), transitions as (p,q) -a→ (δA(p,a), δB(q,a)).
- Mark accepting states as those where one component accepts and the other does not (this accepts symmetric difference).
- Test emptiness by reachability from start: if no accepting pair reachable then L(A)=L(B); else find reachable accepting pair and extract a witness string by recording predecessor transitions.
- This reduces equivalence to emptiness, both decidable.
Common mistakes
- Forgetting to add a dead/completion state before swapping accepting and non-accepting states when complementing a DFA.
- Confusing reversal construction details: when reversing an NFA you must handle multiple final states by creating a new start with ε to each old final, and the new final is the old start.
- For finiteness tests, checking only for cycles anywhere — you must check for cycles that are reachable from start and can reach an accepting state.
For your exam
Question types you will get on this topic:
- Definitions and short notes: define regular language, closure, decidability and list closures with brief constructions.
- Derivations: show closure under intersection with full product construction and formal proof; show complement via swapping states.
- Constructions/diagrams: draw NFA for union, reversed NFA for reversal, product DFA diagram for intersection/equivalence.
- Algorithms: give step-by-step BFS/DFS for emptiness, cycle detection for infiniteness, product construction for equivalence/inclusion.
- Short proofs: reduce inclusion to emptiness; reduce universality to emptiness by complement. A full-marks answer must state assumptions (type of automaton given), give the construction clearly (states, transitions, start, final set), explain why construction works (both directions), and mention complexity or decidability reduction where applicable.
Quick check
- Are regular languages closed under complement? 2. How do you decide if L(D) is empty for a DFA D? 3. How do you test L1 ⊆ L2 for regular languages L1, L2? Answers: 1. Yes — determinize (if needed), complete the DFA, then swap accepting and non-accepting states. 2. Run BFS/DFS from start; if no accepting state is reachable then empty. 3. Check emptiness of L1 ∩ (Σ* \ L2) by building product and complement and testing reachability.
Finished this topic? Mark it so your progress, study plan and readiness keep up.
Stuck on something here?