## 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 s_{0} which
is also final and a state s_{1}. The transitions are as
follows: from each of the two states, we have a transition 0,
ε → a to the state s_{1}, and a transition 1,
a → ε to the state s_{0}. 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.