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

Last 4 digits of your UTEP ID number: ____________________________

1. Let us consider the following grammar (same as in Quiz 3): S → SS; S → a; S → b. The word aba can be generated by this grammar: S → SS → SSS → aSS → abS → aba. Use the Puming Lemma to represent the word aba as uvxyz. Show how the pumped word uvvxyyz can be generated by this grammar.