Skills101
← All practice quizzes

Quiz: Regular Grammars and Finite Automata

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

Regular languages have a third description besides automata and regular expressions — regular grammars. Learn right-linear and left-linear grammars, convert a DFA into a grammar and a grammar into an NFA, handle left-linear grammars by reversal, and see why mixing the two kinds breaks regularity.

Log in to take the quiz

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

  1. Question 1

    Which rule is NOT allowed in a right-linear grammar?

  2. Question 2

    When converting a DFA to a right-linear grammar, what does the arrow P --1--> Q become?

  3. Question 3

    In the DFA-to-grammar method, which variables get an ε-rule?

  4. Question 4

    What does this print?

    delta = {("A", "0"): "B", ("A", "1"): "A", ("B", "0"): "B", ("B", "1"): "C",
             ("C", "0"): "B", ("C", "1"): "A"}
    form, state = "A", "A"
    for ch in "001":
        state = delta[(state, ch)]
        form = form[:-1] + ch + state
    print(form)
    
  5. Question 5

    When converting a right-linear grammar to an NFA, what does the rule A → b become?

🎯 Today’s placement challenge — 10 questions, no login. Can you score 10/10?Take today’s challenge →