## CS 3350 Automata, Computability, and Formal Languages Spring 2016, Test 2

Name: __________________________________________________________

1. Use the algorithm that we had in class to transform the following context-free grammar into Chomsky normal form: S --> BB, S --> BSb, S --> bA, A --> aB, A --> ε, B --> ε.

2. Use the general algorithm to design a (non-deterministic) pushdown automaton that recognizes exactly the context-free language described in Problem 1.

3. In the context-free grammar described in Problem 1, we can derive the sequence bab as follows:
• first, we use the rule S --> BSb;
• then, we use the rules B --> ε and S --> bA;
• after that, we use the rule A --> aB;
• finally, we use the rule B --> ε.
Draw a tree that describes this derivation. Use this tree to determine the subdivision of this sequence into u, v, x, y, and z. Then, for i = 0 and i = 2, draw trees explaining how the corresponding sequences uvixyiz can be derived in this grammar.

4. Use pumping lemma for pushdown automata to prove that the language consisting of all the words of the type a3nb2ncn cannot be recognized by a pushdown automaton.

5. Use the general algorithm to design a context-free grammar that is equivalent to the following finite automaton. This automaton has two states:
• a state q1 which is both a start state and a final state, and
• a state q2.
In the state q1, 1 leads to q2, and 0 leads to q1. In the state q2, 1 leads to q2, and 0 leads to q1.

6. Use the general algorithm to design a Turing machine that is equivalent to a finite automaton from Problem 5.

7. Use the general stack-based algorithms to show:
• how the compiler will transform the expression 2 * (3 * 4 − 5) into inverse Polish notation, and
• how it will compute the value of this expression.

8-9. Design a Turing machine that computes the function n + 2: Trace it on the example of n = 1. Show, step-by-step, how the tape of the Turing machine can be represented as two stacks.

10. Computability and feasibility:
• Formulate Church-Turing thesis.
• Is it a mathematical theorem? A statement about the physical world?
• Formulate the current definition of a feasible algorithm.
• For extra credit: Explain why this definition is not perfect.