CS 3350 Automata, Computability, and Formal Languages
Fall 2017, Test 2

Name: __________________________________________________________

General comments:

Good luck!

1. Design a pushdown automaton that would recognize the words of the type a2nbn, i.e., the language L = {Λ, aab, aaaabb, ...}. Show, step by step, how your pushdown automaton will recognize the word aab. Hint: use a pushdown automaton for recognizing the words of the type anbn as a sample. The difference is that in that case, when we saw a letter 'b', we popped one symbol 'a' from the stack. Now it is slightly different.

2. Design a context-free grammar that would generate all the words of the type a2nbn, i.e., the language L = {Λ, aab, aaaabb, ...}. Show, step by step, how your grammar will generate the word aab. Hint: use a context-free grammar for generating the words of the type anbn as a sample. There, we had rules S → ε and S → aSb, now a slight modification is needed.

3. Use a general algorithm that we had in class to generate a context-free grammar that corresponds to the following finite automaton for recognizing signed or unsigned binary integers. This automaton has three states: the stating state s, the final state f, and the sink state k.
  • From s, any symbol (+, −, 0, or 1) lead to f.
  • From f, 0 or 1 lead to f, while + or − lead to sink.
Show, step by step, how your grammar generates a string +01.

4. Transform, step by step, the grammar with rules S → ε and S → 1S0 to Chomsky normal form. Show how the word 10 will be generated in the resulting Chomsky-normal-form grammar.

5. Use a general algorithm for transforming CFG into PDA to design a pushdown automaton which is equivalent to the the grammar with rules S → ε and S → 1S0. Show, step by step, how the word 10 will be accepted by the resulting pushdown automaton.

6. Use the general stack-based algorithms to show:
  • how the compiler will transform the expression (11 + 1) / (20 − 17) into postfix form, and
  • how it will compute the value of the resulting postfix expression.

7. 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 1-state s1 and the 0-state s0. Both states are final. The transitions are:
  • From s1 to s1, the transition is 1, ε → 1.
  • From s1 to s0, the transition is 0, 1 → ε.
  • From s0 to s0, the transition is 0, 1 → ε.
Show, step by step, how the word 10 will be generated by the resulting grammar.