AlgoVerse

Regular grammar to automaton

Build the automaton for a regular grammar (rules like A → aB): each nonterminal is a state and each rule an edge; then try a string on it.

In a regular (right-linear) grammar each rule is either A → aB (the symbol a, then the nonterminal B) or A → a (a last symbol). That is exactly the shape of an automaton:

Read the full explanation ↓
Input:
rules="S=aS|bA;A=bA…" · w="aabb"PDF export

S → aS | bA, A → bA | b: strings of a's followed by at least two b's. aabb belongs to the language.

  1. def grammar_to_automaton(rules, w):
  2. # rules like "S=aA|b;A=bS": capital letters are nonterminals, small letters terminals.
  3. # Each rule A → aB becomes an edge A --a--> B, and A → a an edge A --a--> F (the final state).
  4. states = []
  5. edges = []
  6. for rule in rules.split(";"):
  7. if "=" not in rule:
  8. return None
  9. lhs, rhs = rule.split("=")
  10. if lhs not in states:
  11. states.append(lhs)
  12. for option in rhs.split("|"):
  13. target = option[1] if len(option) > 1 else "F"
  14. edges.append([lhs, option[0], target])
  15. states.append("F")
  16. # Run the automaton on w, keeping every state it could be in.
  17. current = [states[0]]
  18. for i in range(len(w)):
  19. reached = set()
  20. for s, a, t in edges:
  21. if s in current and a == w[i]:
  22. reached.add(t)
  23. current = sorted(reached)
  24. accepted = "F" in current
  25. return accepted

Invariant: A string x derives from nonterminal A exactly when the automaton reaches F from state A by reading x.

Start

0123
aabb
states—
current—

The table is still empty.

Local variables

rules'S=aS|bA;A=bA|b'
w'aabb'

Orange = changed in this step

Call stack

  1. grammar_to_automaton()line 1
Step 1 of 86
Black = production, read · Orange = key stepnonterminal: 0/2 · production: 0/4 · read: 0/4 · verdict: 0/1
    Explanation

    The idea

    In a regular (right-linear) grammar each rule is either A → aB (the symbol a, then the nonterminal B) or A → a (a last symbol). That is exactly the shape of an automaton:

    • each nonterminal is a state; the start symbol is the start state;
    • A → aB is an edge A --a--> B;
    • A → a is an edge A --a--> F, where F is a new final state.

    A string is in the grammar's language exactly when the automaton reaches F from the start state by reading it. So regular grammars and finite automata describe exactly the same languages.

    The input

    Rules are separated by ; and options by |: for example S=aS|bA;A=bA|b. Capital letters are nonterminals and small letters terminals. The automaton may be nondeterministic, so a set of states is followed at once.