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.