Spring 2020, 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 when answering to the first part of the question, you got a wrong automaton, but on the second part, you correctly traced the new automaton, you will get full credit for the second part.

1. Use a general algorithm to construct a (non-deterministic) pushdown automaton that corresponds to the following context-free grammar with the starting variable S: S → dcB; B → cdS; S → ε. Show, step by step, how the word dccd will be accepted by this automaton. Its derivation in the given grammar is straightforward: S → dcB → dccdS → dccd.

2. Design a finite automaton for recognizing binary sequences that
have even number of a's or even number of bs. Assume that the input
strings contain only symbols a and b. The easiest is to have 4
states:

- a final state ee in which we have even number of a's and even number of b's,
- a final state eo, in which we have even number of a's and odd number of b's, and
- similarly defined states oe (odd-even, final) and oo (odd-odd, not final).

3. Use the general algorithm to transform the grammar from Problem
1 into Chomsky normal form.

4. Use the general algorithm to transform the following pushdown
automaton into a context-free grammar. This automaton has 4 states:
*0101*.

- the starting state s,
- the reading state r,
- the checking state c, and
- the final state f.

- From s to r, the transition is:
- ε, ε → $;

- From r to r, the
transitions are:
- 0, ε → 1;
- 1, ε → 0;

- From r to c, we have a jump ε, ε → ε.
- From c to c, the transitions are:
- 0, 0 → ε
- 1, 1 → ε

- From c to f, the only transition is:
- ε, $ → ε.

5. Show, step by step, how the stack-based algorithm will transform
the expression 5 − (3 − 7) into a postfix expression,
and then how a second stack-based algorithm will compute the value
of this postfix expression.

6. For the grammar from Problem 1, show how the word dccd can be
represented as uvxyz in accordance with the pumping lemma for
context-free grammars. Show that the corresponding word uvvxyyz
will be generated by this grammar.