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