Assignment 1

Read Chapters 0 and 1 in the textbook. The NFAs may use epsilon transitions.

1. You have been chose to design the basic finite automata structure for the Poo-Chi toy.

   Click here for the Poo-Chi manual.

   Based on the manual create a finite automaton that describes the actions of Poo-Chi. You do not have to recreate the entire Poo-Chi experience but pick small number of inputs and outputs and describe it by a finite automaton.

2. Problem 0.11, page 27:
   Find the error in the following proof that all horses are the same color.
   CLAIM: In any set of h horses, all horses are the same color.
   PROOF: By induction on h.
   
   Basis: For h = 1. In any set containing just one horse, all horses clearly are the same color.
   Induction step: For k at least 1, assume that the claim is true for h = k and prove that it is true for h = k + 1. Take any set H of k + 1 horses. We show that all the horses in this set are the same color. Remove one horse from this set to obtain the set H1 with just k horses. By the induction hypothesis, all the horses in H1 are of the same color. Now replace the removed horse and remove a different one to obtain the set H2. By the same argument, all the horses in H2 are the same color. Therefore all of the horses in H must be the same color, and the proof is complete.
3. Problem 1.4(l), page 84:
   Give a state diagram of a DFA for the following language over the alphabet {0,1}:
   {w | w contains an even number of 0s or exactly two 1s}
4. Problem 1.5(c), page 84:
   Give an NFA for the language of the previous problem using only six states.
5. Problem 1.9, page 85:
   Prove that every NFA can be converted to an equivalent one that has a single accept state.