Fall 2015, Quiz 3, 12 pm version

1. At some moment of time, the Turing machine has the following configuration:

_ 0 1 1 0 _ 0 1 _ _ ... /|\ | qIf we represent this Turing machine as a finite automaton with two stacks, what will be the contents of these two stacks? Draw.

At the next moment of time, the head moves one step to the right. Draw the new contents of both stacks, and explain what shall we do with the original two stacks to get the new configuration: what shall we pop? what shall we push?

2. Use the general algorithm to transform the following finite
automaton into a context-free grammar. This automaton has three
states: p, q, and r.

- If we see a letter "a", then we go from p to q, from q to r, and from r to p.
- If we see a letter "b", then we go from p to r, from r to q, and from q to p.

One you obtained the corresponding context-free grammar, show how the word abaaaa (which is accepted by the original finite automaton) will be generated by this grammar.

3-4. On the example of the context-free grammar that you obtained in
Problem 2, apply a general algorithm to transform it into Chomsky
normal form.

*Comment:* if you were unable to generate any grammar in Problem 2,
use any grammar with 4 rules (none of which is originally in the Chomsky
normal form).