CS 3350 Automata, Computability, and Formal Languages
Spring 2020, Test 2

Name: ____________________________

General comments:

Good luck!

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: You just need to describe transitions between these states, and which states are final. Show, step-by-step, how your automaton will accept the string aba. Show how the general algorithm will produce a context-free grammar that generates all the words accepted by this automaton -- and only words generated by this automaton. On the example of a word aba accepted by this automaton, show how the tracing of acceptance of this word by the finite automaton can be translated into a generation of this same word by your context-free grammar.

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:
  • the starting state s,
  • the reading state r,
  • the checking state c, and
  • the final state f.
The transitions are as follows:
  • 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:
    • ε, $ → ε.
Show, step-by-step, how the resulting grammar will generate the sequence 0101.

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.