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. This grammar
describes simple arithmetic expressions (E), combining numbers (N) 0 and 1
with + and -. The starting variable is E, the rules are:
E --> N, E --> N+E, N --> 0, N --> 1, E --> N−E.
2. Use the general algorithm to design a (non-deterministic) pushdown automaton that
recognizes exactly the context-free language described in
Problem 1. Show, step-by-step, how a word 1+0 will be accepted by
3. Apply, to pushdown automaton that you designed in Problem 2,
the general algorithm of transforming a pushdown automaton into
a context-free grammar, and show how this new grammar will generate
the word 1+1. (If you are running out of time,
just a few steps of this algorithm will be OK.)
4. In the context-free grammar described in Problem 1, we
can derive the sequence 0+1+1 as follows:
- first, we use the rule E --> N+E;
- then, we use the rules N --> 0 and E --> N+E;
- after that, we use the rules N --> 1 and E --> N;
- finally, we use the rule N --> 1.
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 = 2,
draw a tree explaining how the corresponding
z can be derived in this
5. Use pumping lemma for pushdown automata to prove that the language
consisting of all the words of the type 1n
cannot be recognized by a pushdown automaton. Can you use the same
lemma to prove that the language 1n
generated by a
6. Use the general algorithm to design a Turing machine that is
equivalent to the following finite automaton. This automaton
helps to check whether a person is a saint. The alphabet consists of two
symbols: + ("good deed") and − ("bad deed"). A person is a saint if
he or she performed at least one good deed and none bad deeds. The automaton
has three states: b ("born", starting state), p ("perfect so
far", final state), and i ("imperfect").
- From each state, −
leads to the state i.
- The state i is a sink (once in i, we stay in i).
- From p, + stays in p.
- From b, + leads to p.
Show, step-by-step, how
this Turing machine will reject a sequence consisting of a minus; and a
plus as not
to a saint.
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 = n + 102
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.
- Formulate Church-Turing thesis.
- Is it a mathematical theorem? A statement about the physical world?
- Formulate the halting problem. Is it computable?