# 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 *w*0?
Similarly, if a 1 is read instead, what integer is represented
by *w*1?
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 *w*0? By *w*1?
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.