2020 February 12,

CS 254: Day 16

Carleton College, Joshua R. Davis

A. Problem 4.20. (Hint: .si egaugnal sti tahw tuoba kniht nehT .rediced a ngised tsriF)

Theorem 4.5 says that the language EQ_DFA is decidable. This next problem provides a somewhat different approach to proving the same result: Simply simulate the two DFAs on all strings up to a certain length m, and then make a decision.

B. Let M₁ and M₂ be DFAs. Prove that there exists an integer m ≥ 1 such that, if M₁ and M₂ agree on all strings of length less than m, then they agree on all strings. ("Agree on a string" means that both machines accept the string or both machines reject the string.) In fact, your proof should be constructive: You should give an algorithm for deducing m from M₁ and M₂.

C. Problem 5.15. (Hint: .noisiced sti ekam neht dna sevom m rof tupni sti etalumis nac rediced ruoY .tupni sti morf ecuded nac rediced ruoy hcihw ,m rebmun a si erehT)