Skills101
← All practice quizzes

Quiz: CFG and PDA

5 questionsNo time limitPass: 60%+10 XP on first pass

Grammars that describe nested structure: CFG definitions, derivations and parse trees, ambiguity (the dangling-else and expression grammars), Chomsky Normal Form, the CYK membership algorithm, and pushdown automata for aⁿbⁿ and balanced brackets — all runnable in Python.

Log in to take the quiz

Free account · see your score, answers and explanations, earn XP

  1. Question 1

    Which grammar generates {a^n b^n | n ≥ 0}?

  2. Question 2

    How many parse trees did the ambiguous grammar E → E+E | EE | id give for id+idid?

  3. Question 3

    What extra memory does a pushdown automaton have compared with a finite automaton?

  4. Question 4

    Context-free languages are NOT closed under:

  5. Question 5

    What is the time complexity of the CYK algorithm for a string of length n?