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 uv
ixy
iz 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 a
3nb
2nc
n
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 q
1, 1 leads to
q
2, and 0 leads to q
1. In the state q
2, 1 leads to q
2, and 0 leads to q
1.
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.