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

Source: https://skills101.in/learn/theory-of-computation/toc-regular-grammars-finite-automata — Skills101 free tutorial (Theory of Computation (TOC)). Updated 2026-11-21.

So far a regular language has had two descriptions: a **finite automaton** (DFA or NFA) and a **regular expression**. The [Chomsky hierarchy](https://skills101.in/learn/theory-of-computation/toc-basics-languages) 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:

| Type | Allowed rules (A, B variables, a a terminal) | Example |
|---|---|---|
| **Right-linear** | A → aB, A → a, A → ε | S → aS, S → bA, A → b |
| **Left-linear** | A → 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](https://skills101.in/learn/theory-of-computation/dfa-deterministic-finite-automata), 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 | ε](https://skills101.in/learn-img/theory-of-computation/dfa-to-right-linear.svg)

```python
# 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"))
```

```text
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**:

| Rule | Becomes |
|---|---|
| X → aY | arrow X --a--> Y |
| X → a | arrow 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](https://skills101.in/learn/theory-of-computation/nfa-to-dfa-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](https://skills101.in/learn-img/theory-of-computation/right-linear-to-nfa.svg)

```python
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))
```

```text
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](https://skills101.in/learn/theory-of-computation/pumping-lemma-dfa-minimisation)).

```python
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))
```

```text
['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

| Description | Recognises / generates | Typical exam conversion |
|---|---|---|
| DFA | accepts | NFA → DFA (subset construction) |
| NFA / ε-NFA | accepts | regex → ε-NFA (Thompson) |
| Regular expression | describes | DFA → regex (state elimination, Arden's theorem) |
| Right- or left-linear grammar | generates | DFA ↔ 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 quiz and free certificate: https://skills101.in/learn/theory-of-computation/toc-regular-grammars-finite-automata