## CS 3350 Automata, Computability, and Formal Languages Fall 2015, Quiz 3, 12 pm version

Name: __________________________________________________________

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

```
_  0  1  1  0  _  0  1  _  _ ...
/|\
|
q
```
If 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.
Here p is the starting state, and also p is the only final state.

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).