CPSC 433: Quiz 7
March 7, 2006

Printed Name:________________________________________

"On my honor, as an Aggie, I have neither given nor received unauthorized aid on this academic work. In particular, I certify that I have not received or given any assistance that is contrary to the letter or the spirit of the collaboration guidelines for this assignment."


  1. (3 pts) What is the basic idea for how to convert an arbitrary context-free grammar into an equivalent push-down automaton? Explain what the state(s) correspond to, and what the transition(s) correspond to.

  2. (1 pt) True or False: Every push-down automaton can be converted into an equivalent deterministic push-down automaton.

  3. (1 pt) True or False: There exists an inherently ambiguous language that is accepted by some deterministic push-down automaton.