Automata, Computability, and Formal Languages
Test 2, 12-1: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 --> 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
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
z can be derived in this
4. Use pumping lemma for pushdown automata to prove that the language
consisting of all the words of the type a2n
cannot be recognized by a pushdown automaton.
5. Use the general algorithm to design a context-free grammar that is equivalent to the following
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
, 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?