1. For the following nondeterministic finite state automaton:

[pic]

For each of the eight possible strings of length 3, determine the set of possible states when the string has been processed. Note: Don't forget to use Λ.

2. For the following nondeterministic finite state automaton: Build a deterministic finite state automaton that accepts the same strings. Show the tree construction and label the states of the deterministic finite state automaton, using the convention to label the states as used in Week-by-Week section 3.1.7.3.

[pic]

3. For each of the next 10 words, decide which of the following six machines accept the given word. (ι) Λ (ii) a (iii) b (iv)aa (v) ab (vi)aba (vii) abba (viii) bab (ix)baab (x) abbb

[pic]

4. How many different TGs are there over the alphabet {a b}? Explain your answer.

5. Build a TG that accepts the language L1 of all words that begin and end with the same double letter, either of the form ee . . . ff or ff . . . rr. Note: eee and fff are not words in this language. That is, the beginning and ending double words cannot overlap. Therefore, ee and ff are also not in this language.

6. Let the language L be accepted by the transition graph T and let L not contain the word Λ. Show how to build a new TG that accepts exactly all the words in L and the word Λ. This problem refers to a transition graph in general, not one specific transition graph. Making the start state also an accepting state is not the correct solution.

7. Given TG1 that accepts L1, show how to build a TG that accepts the language L*. (Hint: see the textbook, page 90, question 12 (ii). Remember L+ is a subset of L*.