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