← All topics
Quiz: CFG and PDA: questions with answers
10 questions, each with the answer and a short explanation.
Take the timed quiz + get a certificate →- Q1. Which grammar generates {a^n b^n | n ≥ 0}?
- Q2. How many parse trees did the ambiguous grammar E → E+E | EE | id give for id+idid?
- Q3. What extra memory does a pushdown automaton have compared with a finite automaton?
- Q4. Context-free languages are NOT closed under:
- Q5. What is the time complexity of the CYK algorithm for a string of length n?
- Q6. Which derivation of aabb uses the grammar S → aSb | ε correctly?
- Q7. A grammar is ambiguous when:
- Q8. In CNF, how many steps does a derivation of a string of length 5 take?
- Q9. What does this print? (code)
- Q10. Why are deterministic PDAs weaker than nondeterministic PDAs?