Fall 2018, Test 3

General comments:

- you are allowed up to 5 pages of handwritten notes;
- if you need extra pages, place your name on each extra page;
- the main goal of most questions is to show that you know the corresponding algorithms; so, if you are running out of time, just follow the few first steps of the corresponding algorithm.

1-2. Transform, step by step, the grammar with rules S →
ε, S → aSb, and S → bSa to Chomsky normal form.
Show how the word baba will be generated in the resulting
Chomsky-normal-form grammar.

3-4. Use a general algorithm for transforming PDA into CFG to design
a CFG that corresponds to the following pushdown automaton. This
automaton has two states: the starting 0-state s_{0} and
the 1-state s_{1}. Both states are final. The transitions
are:

- From s
_{0}to s_{0}, the transition is 0, ε → y, for some symbol y - From s
_{0}to s_{1}, the transition is 1, y → ε. - From
s
_{1}to s_{1}, the transition is 1, y → ε.

5. Use the general stack-based algorithms to show:

- how the compiler will transform the expression (1 − 10) / (8 − 11) into postfix form, and
- how it will compute the value of the resulting postfix expression.

6. Illustrate the pumping lemma for context-free grammars by
showing how it will represent the word w = +1.00 which is generated
by the CFG with starting variable V and rules V → SN.N,
V → N.N, S → +, S → −,
N → DN, N → D, D
→ 0, and D → 1 as uvxyz. Show, step-by-step, how the
corresponding word uvvxyyz can be derived from this CFG.

7. Prove that the language of all the words of the type
a^{n}b^{n}c^{n}d^{n}, n = 0, 1, 2,
..., is not context-free.

8. Design a Turing machine that, given a positive unary number n,
adds 2 to this number. Test it, step-by-step, on the example of n
= 0.

9. (For extra credit)
Design a Turing machine that, given two unary numbers, computes
their sum. The input is represented as two numbers separated by
blank space. Test it, step-by-step, on the example of 2 + 2.

10. (For extra credit)
Let us consider possibly signed binary integers. Such numbers
can be described by the following finite automaton. This automaton
has a starting state s, an intermediate state i, a final state f,
and a sink state k, and the following transitions:

- from s, + or − lead to i, while 0 or 1 lead to f;
- from i, 0 or 1 lead to f, while + or − leads to sink;
- from f, 0 or 1 lead to f, while + or − lead to sink.