Homework #1 FAQ

Problem #1

Question: Can you have an induction in which there is more than one basis case?
Answer: Yes. In fact it appears that the simplest proof for this problem involves an induction where you assume the statement for a string whose length is TWO less than the string you need to prove something about. Thus, you need basis cases for strings of length 0 and 1. As a further hint, if you wish it, consider a string w of length n, and write it as axb, where x is a string of length n-2.

Problem #2

Question: I'm stuck on Problem 2.
Answer: That's not a question, but here's a hint anyway. First, remember that a finite automaton can only remember a little about the past. Fortunately, in this case, a remainder is all we need. To start, suppose that in the past, a string of bits w has been read by the DFA. If string w represents integer n, and a 0 is the next bit read, what integer (in terms of n) is now represented; i.e., what integer is represented by w0? Similarly, if a 1 is read instead, what integer is represented by w1? Of course we don't know what w or n are. However, we can know the remainder when n is divided by 5; we use the state to remember it. If the (integer represented by the) previously read bits w have remainder r, what is the remainder of the integer represented by w0? By w1? If you know about modular arithmetic, you can answer those questions by arithmetic expressions involving the mod operator (% in C). However, even if you don't, there are only five different remainders, so you can figure out the answer for each case. Now, you have all you need to specify the DFA.

Problem #4

Question: If an arc is labeled by both 0 and 1, does it count as two arcs or one?
Answer: It's still only one arc.