[Overview] [Previous] [Next]

Closure III: Intersection and Set Difference

Just as with the other operations, you prove that regular languages are closed under intersection and set difference by starting with automata for the initial languages, and constructing a new automaton that represents the operation applied to the initial languages. However, the constructions are somewhat trickier.

In these constructions you form a completely new machine, whose states are each labeled with an ordered pair of state names: the first element of each pair is a state from L1, and the second element of each pair is a state from L2. (Usually you won't need a state for every such pair, just some of them.)

  1. Begin by creating a start state whose label is (start state of L1, start state of L2).
  2. Repeat the following until no new arcs can be added:
    1. Find a state (A, B) that lacks a transition for some x in sigma.
    2. Add a transition on x from state (A, B) to state (delta(A, x), delta(B, x)). (If this state doesn't already exist, create it.)
The same construction is used for both intersection and set difference. The distinction is in how the final states are selected.

Intersection: Mark a state (A, B) as final if both (i) A is a final state in L1, and (ii) B is a final state in L2.

Set difference: Mark a state (A, B) as final if A is a final state in L1, but B is not a final state in L2.


Copyright 1996 by David Matuszek
Last modified Feb 13, 1996