Automata, Computability, and Formal Languages
1. Use the algorithm that we had in class to transform the
following context-free grammar into Chomsky normal form:
S --> BB, S --> BSb, S --> bA, A --> aB, 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 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
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 a3n
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
, 1 leads to
, and 0 leads to q1
. In the state q2
, 1 leads to q2
, and 0 leads to q1
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.