Skills101

AdvancedTheory of Computation (TOC) · Lesson 14 of 14 · Updated ·

Regular Grammars and Finite Automata — Right-Linear and Left-Linear Grammars, DFA to Grammar and Grammar to NFA

So far a regular language has had two descriptions: a finite automaton (DFA or NFA) and a regular expression. The Chomsky hierarchy adds a third one at its lowest level: the regular grammar (Type 3). Exams ask you to convert between grammars and automata in both directions, and to recognise when a grammar is regular. The conversions are almost mechanical once you see that a variable plays the role of a state.

1. Right-linear and left-linear grammars

A grammar is a set of rules (productions) with variables in capitals and terminals in small letters. A regular grammar restricts the shape of every right side:

TypeAllowed rules (A, B variables, a a terminal)Example
Right-linearA → aB, A → a, A → εS → aS, S → bA, A → b
Left-linearA → Ba, A → a, A → εS → Sa, S → Ab, A → b

In a right-linear grammar the variable is always at the right end, so a derivation grows the string from left to right, one terminal at a time: S ⇒ aS ⇒ abA ⇒ abb. That is exactly how an automaton reads input.

Some books allow a string of terminals instead of a single one (A → abB). That gives the same class of languages, because A → abB can be split into A → aX, X → bB.

Important: a grammar is regular only if all its rules are right-linear, or all are left-linear. Mixing the two kinds is not allowed (section 5 shows why).

2. DFA → right-linear grammar

Give each state its own variable. The start state becomes the start symbol. Then:

  • every arrow X --a--> Y becomes the rule X → aY;
  • every accepting state X gets the rule X → ε.

We use the DFA for "binary strings ending in 01" from the DFA lesson, with states renamed A, B, C.

DFA for strings ending in 01 with states A, B and accepting C, and the grammar read off it: A → 0B | 1A, B → 0B | 1C, C → 0B | 1A | ε

# DFA for binary strings ending in 01 (states A, B, C; C is accepting)
delta = {("A", "0"): "B", ("A", "1"): "A",
         ("B", "0"): "B", ("B", "1"): "C",
         ("C", "0"): "B", ("C", "1"): "A"}
accepting = {"C"}

# one rule X -> aY per arrow, and X -> ε for every accepting state
rules = {}
for (x, a), y in delta.items():
    rules.setdefault(x, []).append(a + y)
for x in accepting:
    rules[x].append("ε")
for x, bodies in rules.items():
    print(x, "->", " | ".join(bodies))

def derivation(word, start="A"):
    form, state, steps = start, start, [start]
    for ch in word:
        state = delta[(state, ch)]
        form = form[:-1] + ch + state          # replace the variable at the end by "ch state"
        steps.append(form)
    if state in accepting:
        steps.append(form[:-1])                # use X -> ε
        return " => ".join(steps)
    return " => ".join(steps) + "  (stuck: " + state + " has no ε-rule)"

print(derivation("1101"))
print(derivation("110"))
A -> 0B | 1A
B -> 0B | 1C
C -> 0B | 1A | ε
A => 1A => 11A => 110B => 1101C => 1101
A => 1A => 11A => 110B  (stuck: B has no ε-rule)

The derivation copies the run of the DFA. After reading 110 the DFA is in B, and the sentential form is 110B. A string is generated exactly when the run ends in an accepting state, because only then can the last variable vanish with X → ε. For 110 the run ends in B, which has no ε-rule, so 110 cannot be generated.

If your syllabus does not allow ε-rules, use the other standard form: for an arrow X --a--> Y into an accepting state Y, also add X → a. Here that gives B → 1C | 1 (only the empty string then needs special care).

3. Right-linear grammar → NFA

Reverse the idea. Each variable becomes a state, the start symbol becomes the start state, and add one new final state F:

RuleBecomes
X → aYarrow X --a--> Y
X → aarrow X --a--> F
X → εX is an accepting state

The result may be an NFA (a variable can have two rules with the same terminal, like A → bA | b). That is fine: subset construction turns it into a DFA if needed.

NFA built from the grammar S → aA, A → aA | bA | b: S goes to A on a, A loops on a and b, and A goes to the final state F on b

import re
from itertools import product

# right-linear grammar: strings over {a, b} that start with a and end with b
grammar = {"S": ["aA"], "A": ["aA", "bA", "b"]}

# variable = state; X -> aY is an arrow X --a--> Y; X -> a is an arrow X --a--> F
nfa = {}
for x, bodies in grammar.items():
    for body in bodies:
        target = body[1:] if len(body) == 2 else "F"
        nfa.setdefault((x, body[0]), set()).add(target)
final = {"F"} | {x for x, bodies in grammar.items() if "" in bodies}
for (x, a), targets in sorted(nfa.items()):
    print(f"{x} --{a}--> {sorted(targets)}")

def accepts(word):
    current = {"S"}
    for ch in word:
        current = set().union(*[nfa.get((q, ch), set()) for q in current])
    return bool(current & final)

words = ["".join(t) for n in range(9) for t in product("ab", repeat=n)]
print("agrees with regex a(a|b)*b on", len(words), "strings:",
      all(accepts(w) == bool(re.fullmatch("a(a|b)*b", w)) for w in words))
A --a--> ['A']
A --b--> ['A', 'F']
S --a--> ['A']
agrees with regex a(a|b)*b on 511 strings: True

The grammar describes strings that start with a and end with b. The NFA built from it agrees with the regular expression a(a|b)*b on every string up to length 8.

4. Left-linear grammars: use reversal

In a left-linear grammar the variable is on the left, so a derivation builds the string from right to left: S ⇒ Sa ⇒ Sba ⇒ … . The trick is to reverse everything:

  1. Reverse every right side. A → Ba becomes A → aB. The grammar is now right-linear and generates the reverse of the language, Lᴿ.
  2. Convert that right-linear grammar to an NFA for Lᴿ (section 3).
  3. Reverse the NFA: flip every arrow, make the old final state the start, and make the old start state final. This NFA accepts L.

Example: S → Sb | Ab, A → Aa | a generates aᵐbⁿ with m ≥ 1, n ≥ 1. Reversing the bodies gives S → bS | bA, A → aA | a, which generates bⁿaᵐ — the reverse language. Because regular languages are closed under reversal, both are regular.

This also gives the key fact: left-linear grammars and right-linear grammars generate exactly the same class of languages — the regular languages.

5. Mixing left and right rules breaks regularity

Each rule below on its own looks harmless:

S → aA (right-linear) A → Sb | ε (A → Sb is left-linear)

But together they generate a, aab, aaabb, … — that is aⁿ⁺¹bⁿ. The rule A → Sb puts a b to the right of every new a, so the grammar can match counts, which no finite automaton can do (see the pumping lemma lesson).

def words(g, start, n):
    """All terminal strings of length <= n that the grammar derives."""
    gen = {v: set() for v in g}
    changed = True
    while changed:
        changed = False
        for v, bodies in g.items():
            for b in bodies:
                parts = {""}
                for s in b:
                    options = gen[s] if s in g else {s}
                    parts = {p + q for p in parts for q in options if len(p + q) <= n}
                if not parts <= gen[v]:
                    gen[v] |= parts
                    changed = True
    return gen[start]

# S -> aA (right-linear rule)   A -> Sb | ε (left-linear rule)
mixed = {"S": [("a", "A")], "A": [("S", "b"), ()]}
print(sorted(words(mixed, "S", 8), key=len))
['a', 'aab', 'aaabb', 'aaaabbb']

So a grammar with some right-linear and some left-linear rules is called linear, not regular. Linear grammars can generate non-regular languages such as aⁿbⁿ.

6. Four descriptions of one class

DescriptionRecognises / generatesTypical exam conversion
DFAacceptsNFA → DFA (subset construction)
NFA / ε-NFAacceptsregex → ε-NFA (Thompson)
Regular expressiondescribesDFA → regex (state elimination, Arden's theorem)
Right- or left-linear grammargeneratesDFA ↔ grammar (this lesson)

All four describe exactly the regular languages. When a question asks "is this language regular?", any one of them is enough proof.

Common mistakes

  • Calling a grammar regular when it mixes A → aB and A → Ba rules. It must be all right-linear or all left-linear.
  • Forgetting X → ε (or X → a) for accepting states, so the grammar never finishes a derivation.
  • Forgetting the new final state F when converting A → a to an NFA arrow.
  • Converting a left-linear grammar by just moving the variable to the right without reversing the whole automaton. That gives the reverse language.
  • Expecting the grammar from section 3 to give a DFA. It often gives an NFA, which is still correct.

Quick recap

  • Right-linear: A → aB | a | ε. Left-linear: A → Ba | a | ε. Regular = all of one kind.
  • DFA → grammar: arrow X --a--> Y gives X → aY; accepting X gives X → ε.
  • Grammar → NFA: variables become states; X → a goes to a new final state F; X → ε makes X accepting.
  • Left-linear: reverse the bodies, build the NFA, reverse the NFA.
  • Mixed linear rules can generate aⁿbⁿ, so they are not regular grammars.

Practice what you learned

📝 Quiz: Regular Grammars and Finite Automata5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →