Problem 1: On the strange planet described in this Slide Set, suppose there are n individuals, and states are triples (i,j,k) of the number of individuals of species a, b, and c, respectively. How many states are there? Note: this question should be solvable from the combinatorics you learned in CS103 or equivalent. Chapter four of Foundations of Computer Science covers this material if you need a review or catch-up.
Problem 2: Here is the transition table of a DFA:
| 0 | 1 | |
|---|---|---|
| ->A | B | B |
| *B | A | A |
Determine the language accepted by this DFA. Then, give a careful proof of your claim. Remember that you need to prove two directions: the automaton accepts what you claim it accepts, and what you claim it accepts it really does accept. Each direction is an induction. What is the inductive statement in each case? On what parameter is the induction? What is the basis case? Prove it. What is the inductive statement? Prove it. While the ideas for this very simple example are easy, you will be graded on your ability to organize the proof as well as on the correctness of what you say.
Problem 3 Design a DFA that accepts those binary strings w such that when you reverse w you get a binary integer that is divisible by 5. For example, your DFA should accept 10011, because when you reverse it, you get 11001, which as a binary integer is 25 in decimal, and 25 is evenly divisible by 5. Hint: suppose you have read w so far, and the next input is 0. Then both w-reversed and w0-reversed have the same value as a binary integer, so the decision whether w0-reversed is divisible by 5 was already made. However, if 1 is the next input, the integer value of 1 followed by w-reversed is 2i plus the value of w-reversed, where i is the length of w. Unfortunately, you can't remember, using the state of a finite automaton, exactly what i is. The trick is to use five states to remember "just enough" that you can decide whether the reverse of w1 is divisible by 5. Added 3/31/10: It turns out that the hint is not enough to get that 5-state DFA directly. It does give you a larger DFA, from which you can derive the minimum-state DFA with some effort. We'll accept the larger DFA if you don't want to pursue the matter to its conclusion.
Note: we're not going to be handing out problems to do for no credit regularly. But it is early in the quarter, and projects aren't due for a while. So if you want something to do that is les fattening that lying around and drinking beer, you can work up a sweat over these.
Problem 4: Suppose there are 100 individuals on the strange planet. If states represent sorted lists of species counts, how many states are there? Even better: can you give the general rule for n individuals?
Problem 5: Analyze the strange planet. For what numbers of individuals are there can't-fail states? When are there must-fail states other than the states where all individuals are of one species? If you would like a hint, you may look at the Hint File at any time. We will read any observations you make, even if you don't "nail" the problem completely.