The example discussed in the problem is below.

Problem 5* [20 pts] Consider the example in lecture 3 of a DFA that accepted the language of all binary numbers that are divisible by 3. It had 3 states. Do you think it is possible to design a DFA with only two states that accepts precisely this language? If so, demonstrate it with a two-state DFA and a proof that the accepted language is precisely binary strings representing numbers divisible by 3. Otherwise, prove that such a two-state DFA is impossible. Example: Binary numbers divisible by 3 q1 go q2 Induction Hypothesis Claim: 6A(qo,x)- qo iff x mod30