# Fall 2008 The Chinese University of Hong Kong Fall 2008 The Chinese University of Hong Kong CSC 3130: Automata theory and formal languages More on DFA minimization and DFA equivalence Andrej Bogdanov http://www.cse.cuhk.edu.hk/~andrejb/ csc3130 Example Construct a DFA over alphabet {0, 1} that accepts those strings that end in 111 0 0 q 1 q 1

0 q 1 q 1 q q q 1 1 q 1

0 q q 0 q 1 This is big, isnt there a smaller DFA for this? Smaller DFA Yes, we can do it with 4 states: 0 q 1 0

1 q 0 0 q 1 q 1 No smaller DFA! Last time we saw that There is no DFA with 3 states for L In fact, it is also true that This is the unique 4-state DFA for L 0 q 1

0 1 q 0 0 q 1 q 1 Theorem The DFA M found by the minimization algorithm is the unique minimal DFA for L Proof outline Suppose there are two minimal DFAs M, M for L q0 M

q0 M In both M and M, every pair of states is distinguishable Proof outline for uniqueness If M and M are not the same, there must be states q1, q2 of M and q of M like this: u q1 M q0 M q 0 v q2

For some strings u and v q u, v Proof outline for uniqueness Since q1 and q2 are distinguishable, there is a string w such that u v q1 q2 w w M M q u, v

But in M this cannot happen! w ? Testing equivalence of DFAs Two DFAs are called equivalent if they accept the same language 0 0 0 q 1 q 0 1 q 1

q 1 q 1 0 0 0 q 1 0 q q 1 0 q 0 1

qC 1 1 Testing equivalence of DFAs How can we tell if M and M are equivalent? Algorithm for testing DFA equivalence: Run DFA minimization algorithm on M Run DFA minimization algorithm on M Check that M and M are the same Example Do the following two NFAs q 0,1 1 0,1 0

q 0 q 1 1 accept the same language? q 0 Answer We cannot run minimization procedure on NFAs But we can convert both NFAs to DFA and test equivalence regular expression NFA DFA