Skip to content
Tutorials Center
My learning

Topics

Lesson 9 of 59 · Finite Automata

Operations on DFAs: Complement, Union, Concatenation, Reverse

Learn how to build DFAs for the complement, union, intersection, concatenation and reversal of regular languages, with the product construction and Python code.

Regular languages are closed under the usual language operations: if you start with languages that some DFA recognizes, combining them gives a language that some DFA recognizes. The proofs are constructions: recipes that build the new machine. This lesson gives each recipe and implements it, so you can test the result against a plain Python check.

Complement: swap accepting and non-accepting

The complement of L (all strings over Σ not in L) is recognized by the same DFA with accepting and non-accepting states swapped. This works only because a DFA is total: every string follows exactly one path to exactly one state. A string is in L when that state accepts, and in the complement exactly when it does not.

Warning: swapping the final states of an NFA does not give the complement, because "some path accepts" does not become "no path accepts". Convert to a DFA first.

Union and intersection: the product construction

To combine DFAs M1 and M2 (over the same alphabet), run both at the same time. A state of the new machine is a pair (p, q), where p is the current state of M1 and q the current state of M2. On symbol a, it moves to (δ1(p, a), δ2(q, a)). The start state is (start1, start2). The only difference between the operations is which pairs accept:

Operation Accepting pairs (p, q)
Union L1 ∪ L2 p accepts or q accepts
Intersection L1 ∩ L2 p accepts and q accepts
Difference L1 − L2 p accepts and q does not
Symmetric difference exactly one of them accepts

If M1 has m states and M2 has n states, the product has at most m × n states.

Python Complement, union and intersection via the product construction

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All 127 words (every string up to length 6) agree with the set-theoretic definitions. Notice that complement works on the whole transition table, so the dead state, if any, becomes accepting in the complement. That is correct: a string that falls into the dead state is not in L, so it is in the complement.

Reversal: flip the arrows

The reversal L^R contains the reverse of each string in L. To build an automaton for it:

  1. Reverse every transition arrow: if p → q on a, add q → p on a.
  2. Make the old accepting states the start states, and the old start state the only accepting state.

After step 1 the machine is generally an NFA (several states can have an arrow into one state, which becomes several arrows out), and several start states can be handled by a new start state with ε-moves to each. Then use the subset construction to get a DFA again.

Concatenation and Kleene star: build an ε-NFA

To recognize L1 L2, take M1 and M2 and add an ε-arrow from every accepting state of M1 to the start state of M2. Then the accepting states of M1 are made non-accepting; only M2's remain. The machine guesses when the first part of the string ends. For L^* (Kleene star), add a new accepting start state with an ε-arrow into the old start state, and ε-arrows from every old accepting state back to the old start.

flowchart LR
    S["new start"] -.->|"ε"| M1["M1<br/>(start)"]
    M1 -->|"accepting states of M1<br/>ε to start of M2"| M2["M2"]
    M2 --> F((("accept")))

Concatenation: the input is split into an M1 part and an M2 part, and ε-arrows jump from one machine to the other.

Python Reversal and concatenation as epsilon-NFAs

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The reversed machine for "ends in ab" accepts strings that start with ba, as expected. The concatenation test compares the ε-NFA against the definition: some split point i where the prefix is in L1 and the suffix in L2.

Summary of closure results

Regular languages are closed under union, intersection, complement, difference, concatenation, Kleene star and reversal. Closure is a powerful proof tool: to show a language is regular, build it from known regular languages with these operations; to show it is not regular, assume it is and use closure to derive a contradiction (see closure properties).

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. How do you build a DFA for the complement of a language recognized by a total DFA?

    Every string reaches exactly one state, so flipping which states accept flips which strings are accepted.
  2. 2. In the product construction for intersection, a pair (p, q) accepts when...

    Intersection requires the string to be in both languages, so both components must be in accepting states.
  3. 3. M1 has 4 states and M2 has 6. What is the maximum number of states in the product DFA?

    States are pairs (p, q), giving at most 4 x 6 = 24.
  4. 4. Why does swapping accepting states of an NFA not give its complement?

    A string could have one path ending in an accepting state and another in a non-accepting state; after swapping, it may still be accepted. Determinize first.
  5. 5. Which construction needs ε-moves or nondeterminism?

    Concatenation must guess where the first part of the string ends, which naturally uses ε-moves; complement and the product construction stay deterministic.

Summary

  • Complement: swap accepting states of a total DFA.
  • Union, intersection, difference: run two DFAs in parallel (product construction) and change the accepting pairs.
  • Reversal: flip arrows, swap start and accepting roles, then determinize.
  • Concatenation and star: connect machines with ε-moves, then determinize if a DFA is required.

Next: Minimization of DFAs