2018 October 10,

CS 254: Day 14

Carleton College, Joshua R. Davis

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

B. Let EQ_DFA = {< M₁, M₂ > : M₁ and M₂ are DFAs, and L(M₁) = L(M₂)}. Describe a Turing machine that decides EQ_DFA. (Hint: Use Problem A.)