Fall 2015, Test 2, 3-4:20 pm version

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 --> Ba, B --> 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 aba as follows:
^{i}xy^{i}z can be derived in this
grammar.

- first, we use the rule S --> aSA;
- then, we use the rules S --> Ba and A --> ε
- after that, we use the rule B --> Ab;
- finally, we use the rule A --> ε.

4. Use pumping lemma for pushdown automata to prove that the language
consisting of all the words of the type a^{3n}b^{n}c^{2n}
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: _{1}, 0 leads to
q_{1}, and 1 leads to q_{2}. In the state q_{2}, 0 leads to q_{1}, and 1 leads to q_{2}.

- the starting state q
_{1}, and - the final state q
_{2}.

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 = 1. 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?