2018 October 10,

Carleton College, Joshua R. Davis

A. Let *M*_{1} and *M*_{2} be DFAs. Let *p*_{1} and *p*_{2} be their numbers of states. Suppose that *M*_{1} and *M*_{2} agree on all strings of length less than *p*_{1} *p*_{2}. ("Agree on a string" means that both machines accept the string or both machines reject the string.) Prove that *M*_{1} and *M*_{2} agree on all strings.

B. Let *EQ _{DFA}* = {<