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
^{i}xy
^{i}z 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
^{3n}b
^{2n}c
^{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 q_{1} which is both a start state and a final state, and
- a state q_{2}.
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.