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."

Signature:___________________________________________

  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.