Skills101
← All practice quizzes

Quiz: Simplifying CFGs and CNF

5 questions · new set on every retakeNo time limitPass: 60%+10 XP on first pass

Learn the exam procedure for cleaning a context-free grammar: remove useless symbols in the right order, eliminate ε-productions and unit productions, and convert the result to Chomsky Normal Form. Every step is run in Python and the final grammar is checked to generate exactly the same strings.

Log in to take the quiz

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

  1. Question 1

    In the grammar S → AB | a, A → b, B → BC, C → c, which variable is not generating?

  2. Question 2

    Why must non-generating symbols be removed before unreachable ones?

  3. Question 3

    In S → ASA | aB, A → B | S, B → b | ε, which variables are nullable?

  4. Question 4

    A rule A → XYZ has X and Z nullable. How many non-empty bodies does it give after ε-removal?

  5. Question 5

    What does this print?

    from itertools import product
    nullable = {"A"}
    body = ("a", "A", "A")
    choices = [[(s,), ()] if s in nullable else [(s,)] for s in body]
    bodies = {tuple(s for part in pick for s in part) for pick in product(*choices)}
    print(len(bodies))
    
🎯 Today’s placement challenge — 10 questions, no login. Can you score 10/10?Take today’s challenge →