CS 3350 Automata, Computability, and Formal Languages
Fall 2018, Quiz 3

Last 4 digits of your UTEP ID number: ____________________________

1. Use the general algorithm to describe a pushdown automaton that correpsonds to the following context-free grammar: S → SS; S → a; S → b. The word ab can be generated by this grammar: S → SS → aS → ab. Show, step by step, how the above derivation translates into an acceptance of the word ab by the resulting pushdown automaton.