2018 October 10,

CS 254: Day 14

Carleton College, Joshua R. Davis

A. Let M1 and M2 be DFAs. Let p1 and p2 be their numbers of states. Suppose that M1 and M2 agree on all strings of length less than p1 p2. ("Agree on a string" means that both machines accept the string or both machines reject the string.) Prove that M1 and M2 agree on all strings.

B. Let EQDFA = {< M1, M2 > : M1 and M2 are DFAs, and L(M1) = L(M2)}. Describe a Turing machine that decides EQDFA. (Hint: Use Problem A.)