CS 3350 Automata, Computability, and Formal Languages Fall 2015, Test 2, 12-1:20 pm version

Name: __________________________________________________________

1. Use the algorithm that we had in class to transform the following context-free grammar into Chomsky normal form: S --> AA, S --> ASa, S --> aB, B --> bA, 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 aba as follows:
• first, we use the rule S --> ASa;
• then, we use the rules A --> ε and S --> aB;
• after that, we use the rule B --> bA;
• finally, we use the rule A --> ε.
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 a2nbnc3n 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, 0 leads to q2, and 1 leads to q1. In the state q2, 0 leads to q2, and 1 leads to q1.

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

7-8. Design a Turing machine that computes the following function in unary code: f(0) = 0 and f(n) = n − 1 for n > 0. Trace it on the example of n = 2. Show, step-by-step, how the tape of the Turing machine can be represented as two stacks.

9. Formulate Church-Turing thesis. Is it a mathematical theorem? A statement about the physical world?

10. Formulate the current definition of a feasible algorithm. Give two examples explaining why this definition is not perfect:
• an example of an algorithm that is feasible according to this definition but not feasible according to common sense; and
• an example of an algorithm that is feasible from the practical viewpoint but not feasible according to this definition.

11. (For extra credit) Define what it means for a problem to be NP-hard. Can every NP-hard problem be solved by a feasible algorithm?