CPSC 433: Quiz 6
March 2, 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. (2 pts) Give an intuitive description of a push-down automaton.

  2. (1 pt) True or False: The language consisting of all odd length palindromes over {0,1} is accepted by some push-down automaton by final state.

  3. (1 pt) True or False: For every language L that is accepted by a push-down automaton M by final state, L is also accpeted by M by empty stack.

  4. (1 pt) True or False: Every context-free grammar can be converted into an equivalent push-down automaton.