Additional Exercise 1
Consider some DFA M in which all transitions are specified.
We say that states p and q of M are distinguishable
if and only if there exists some string x such that delta(p,x) is
in F and delta(q,x) is not in F or vice versa.
Knowing that M has n states and that p and q
are distinguishable, derive and prove an upper bound on the length of a shortest
distinguishing string x.
Additional Exercise 2
Devise an algorithm to decide wether or not two DFAs (on the same alphabet)
accept the same language, knowing only the alphabet and the number of states
in each DFA. How much time can your algorithm take as a function of the
number of states of each machine?
