Fall 2016, Test 2

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
this automaton.

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:
^{i}xy^{i}z can be derived in this
grammar.

- 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.

5. Use pumping lemma for pushdown automata to prove that the language
consisting of all the words of the type 1^{n}0^{n}1^{n}0^{n}
cannot be recognized by a pushdown automaton. Can you use the same
lemma to prove that the language 1^{n}0^{n} cannot be
generated by a
context-free grammar?

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").
*not* corresponding
to a saint.

- 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.

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 + 10_{2}
in
binary.
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:

- Formulate Church-Turing thesis.
- Is it a mathematical theorem? A statement about the physical world?
- Formulate the halting problem. Is it computable?