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

Last 4 digits of your UTEP ID number: ____________________________

1. 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 state s0 which is also final and a state s1. The transitions are as follows: from each of the two states, we have a transition 0, ε → a to the state s1, and a transition 1, a → ε to the state s0. Show, step by step, how the word 0011 will be generated by the resulting grammar. For extra credit: show also how the word 0101 will be generated.