Spring 2017, Test 2

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 of time, just follow the few first steps of the corresponding algorithm;
- each question will be graded on its own merit; so, for example, if on one stage, you got a wrong context-free grammar, but on the second stage, you correctly apply the Chomsky normal form algorithm to the resulting grammar, you will get full credit for the second stage.

1-4. *Finite automata.* Let us consider the following finite
automaton (FA) for recognizing words in the alphabet {a,b} that
only have a's (and do not have any b's). This automaton has two
states: the start state which is also final, and the sink state.
From the start state, letter 'a' leads back to the same state,
while letter 'b' leads to the sink state.
5-8. *Pushdown automata (PDA) and context-free grammars
(CFG).* The following CFG generates the language
{p^{n}q^{n}}: it has the starting variable S and
the rules S → ε, S → pSq.
9. Use the general stack-based algorithms to show:

1. On the example of the word aaa accepted by the given automaton,
show how this word will be represented as xyz according to the
pumping lemma for FA. For this sequence, check -- by tracing
step-by-step -- that the sequence xy^{2}z is indeed
accepted by this automaton.

2. Use the general algorithm to transform the given FA into a context-free grammar (CFG). Show, step-by-step, how the word aaa can be derived in this CFG.

3. Use the general algorithm to transform the given FA into a Turing machine (TM). Show, step-by-step, how this TM will accept the word aaa.

4. Use the Pumping Lemma for FA to prove that the language
{p^{n}q^{n}} = {Λ, pq, ppqq, pppqqq, ...}
cannot be recognized by a finite automaton.

5. Show, step-by-step, how the word ppqq will be generated by this CFG.

6. Use the general algorithm to generate a PDA that recognizes the words generated by this CFG -- and only these words. Show, step-by-step, how the resulting PDA will accept the word ppqq.

7. Use the general algorithm to transform the given CFG into Chomsky normal form.

8. On the example of the word ppqq generated by the given CFG,
show how this word will be represented as uvxyz according to the
pumping lemma for CFG. For this sequence, check -- by tracing
step-by-step -- that the sequence uv^{2}xy^{2}z is
indeed generated by this CFG.

- how the compiler will transform the expression (2 − 4) * (1 + 3) into postfix form, and
- how it will compute the value of the resulting postfix expression.

10. Design a Turing machine (TM) for subtracting 1 from the input
n in binary code; assume that the input is non-zero. Trace,
step-by-step, how your TM will perform when n = 10_{2}
(i.e., when n is equal to number 2 as described in the binary
code).