Regular Language Equivalence and DFA Minimization
Regular Language Equivalence and DFA Minimization
Regular Language Equivalence and DFA Minimization
1
Decision Property: Equivalence
• Given regular languages L and M, is
L = M?
• Algorithm involves constructing the
product DFA from DFA’s for L and M.
• Let these DFA’s have sets of states Q
and R, respectively.
• Product DFA has set of states Q × R.
• I.e., pairs [q, r] with q in Q, r in R.
2
Product DFA – Continued
• Start state = [q0, r0] (the start states of
the DFA’s for L, M).
• Transitions: δ([q,r], a) =
[δL(q,a), δM(r,a)]
• δL, δM are the transition functions for the
DFA’s of L, M.
• That is, we simulate the two DFA’s in the
two state components of the product DFA.
3
Example: Product DFA
0 0
1 0
A B [A,C] [A,D]
0, 1 1
1 1 0
0
1 [B,C] [B,D]
0 1
0
C D
4
Equivalence Algorithm
• Make the final states of the product DFA
be those states [q, r] such that exactly
one of q and r is a final state of its own
DFA.
• Thus, the product accepts w iff w is in
exactly one of L and M.
5
Example: Equivalence
0 0
1 0
A B [A,C] [A,D]
0, 1 1
1 1 0
0
1 [B,C] [B,D]
0 1
0
C D
6
Equivalence Algorithm – (2)
• The product DFA’s language is empty
iff L = M.
• But we already have an algorithm to
test whether the language of a DFA is
empty.
7
Decision Property: Containment
• Given regular languages L and M, is
L ⊆ M?
• Algorithm also uses the product
automaton.
• How do you define the final states [q, r]
of the product so its language is empty
iff L ⊆ M?
Answer: q is final; r is not.
8
Example: Containment
0 0
1 0
A B [A,C] [A,D]
0, 1 1
1 1 0
0
1 [B,C] [B,D]
0 1
0
C D
Note: the only final state
1 is unreachable, so
containment holds.
9
The Minimum-State DFA for a
Regular Language
• In principle, since we can test for
equivalence of DFA’s we can, given a
DFA A find the DFA with the fewest
states accepting L(A).
• Test all smaller DFA’s for equivalence
with A.
• But that’s a terrible algorithm.
10
Efficient State Minimization
• Construct a table with all pairs of states.
• If you find a string that distinguishes
two states (takes exactly one to an
accepting state), mark that pair.
• Algorithm is a recursion on the length of
the shortest distinguishing string.
11
State Minimization – (2)
• Basis: Mark a pair if exactly one is a final
state.
• Induction: mark [q, r] if there is some
input symbol a such that [δ(q,a), δ(r,a)]
is marked.
• After no more marks are possible, the
unmarked pairs are equivalent and can
be merged into one state.
12
Transitivity of “Indistinguishable”
• If state p is indistinguishable from q,
and q is indistinguishable from r, then p
is indistinguishable from r.
• Proof: The outcome (accept or don’t)
of p and q on input w is the same, and
the outcome of q and r on w is the
same, then likewise the outcome of p
and r.
13
Constructing the Minimum-
State DFA
• Suppose q1,…,qk are indistinguishable
states.
• Replace them by one state q.
• Then δ(q1, a),…, δ(qk, a) are all
indistinguishable states.
• Key point: otherwise, we should have
marked at least one more pair.
• Let δ(q, a) = the representative state
for that group. 14
Example: State Minimization
r b r b
{1} {2,4} {5} AB C
{2,4} {2,4,6,8} {1,3,5,7} BD E
Here it is
{5} {2,4,6,8} {1,3,7,9} CD F
with more
{2,4,6,8} {2,4,6,8} {1,3,5,7,9} DD G
convenient
ED G
{1,3,5,7} {2,4,6,8} {1,3,5,7,9} state names
* {1,3,7,9} {2,4,6,8} {5} *F D C
* {1,3,5,7,9} {2,4,6,8} {1,3,5,7,9} *G D G
Replace D and E by H.
Result is the minimum-state DFA.
21
Eliminating Unreachable States
• Unfortunately, combining
indistinguishable states could leave us
with unreachable states in the
“minimum-state” DFA.
• Thus, before or after, remove states
that are not reachable from the start
state.
22