## 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.