Regular Language Equivalence

and DFA Minimization

Equivalence of Two Regular Languages
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

Remember this DFA? It was constructed for the

chessboard NFA by the subset construction.
15
 Example – Continued
r b G F E D C B
AB C A x x
BD E B x x
CD F C x x
DD G D x x
ED G E x x
*F D C F
*G D G

Start with marks for

the pairs with one of
the final states F or G. 16
 Example – Continued
r b G F E D C B
AB C A x x
BD E B x x
CD F C x x
DD G D x x
ED G E x x
*F D C F
*G D G

Input r gives no help,

because the pair [B, D]
is not marked. 17
 Example – Continued
r b G F E D C B
AB C A x x x x x
BD E B x x x x x
CD F C x x
DD G D x x
ED G E x x
*F D C F x
*G D G
But input b distinguishes {A,B,F}
from {C,D,E,G}. For example, [A, C]
gets marked because [C, F] is marked.
18
 Example – Continued
r b G F E D C B
AB C A x x x x x
BD E B x x x x x
CD F C x x x x
DD G D x x
ED G E x x
*F D C F x
*G D G
[C, D] and [C, E] are marked
because of transitions on b to
marked pair [F, G].
19
 Example – Continued
r b G F E D C B
AB C A x x x x x x
BD E B x x x x x
CD F C x x x x
DD G D x x
ED G E x x
*F D C F x
*G D G
[A, B] is marked [D, E] can never be marked,
because of transitions on r because on both inputs they
to marked pair [B, D]. go to the same state. 20
 Example – Concluded
r b r b G F E D C B
AB C AB C A x x x x x x
BD E BH H B x x x x x
CD F CH F C x x x x
DD G HH G D x x
ED G E x x
*F D C *F H C F x
*G D G *G H 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