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

Last 4 digits of UTEP ID: ____________________________

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