Right-Linear Grammars and the Limits of One-Way Derivation

A regular expression and a finite automaton describe the same languages by two different mechanisms. A grammar gives a third, and the surprise is how narrow it must be to stay inside the class. The restriction is not on the number of rules or their length; it is on the position of the nonterminal inside each right-hand side.

The shape restriction

A grammar is right-linear when every production has one of two forms:

A → aB     A → a     A → ε

where A and B are nonterminals and a is a terminal. Each rule consumes exactly one terminal and leaves at most one nonterminal, always at the right end. A grammar is left-linear when the nonterminal, if present, is at the left end: A → Ba, A → a, A → ε. A regular grammar is one that is either right-linear or left-linear throughout; mixing the two orientations in one grammar is not a regular grammar in the standard definition, for reasons that appear below.

The right-linear restriction makes derivation a left-to-right scan. Starting from S, each step emits one terminal and hands control to a single successor nonterminal. After k steps the sentential form is a string of k terminals followed by at most one nonterminal. Since the terminal prefix never changes again, the derivation is exactly a walk through a state graph, and the grammar is an automaton written in production notation.

The correspondence is a bijection up to renaming. Given a right-linear grammar with nonterminal set V, take V as states, S as the start state, and add a single accepting state F. Then:

• Rule A → aB becomes a transition A —a→ B.
• Rule A → a becomes A —a→ F.
• Rule A → ε becomes an ε-transition A → F.

Every derivation of a string w corresponds to a path labelled w from S to F, and conversely. Given a nondeterministic finite automaton, the same map in reverse yields a grammar with one nonterminal per state and one rule per transition. The constructions preserve size: n states give n nonterminals, m transitions give m productions, and the resulting grammar has no ε-productions unless the automaton accepts the empty string.

What the restriction buys and costs

The grammar view makes the memory bound explicit. A derivation is a sequence of independent local choices with no record of what was emitted earlier; the only thing carried forward is the identity of the current nonterminal. That is a constant amount of information, which is precisely why the class is closed under complement and why equivalence is decidable.

The cost is that nested structure cannot be expressed. The language {aⁿbⁿ : n ≥ 1} requires remembering how many a’s were seen before the first b, and a right-linear grammar has nowhere to put that count. Any attempt runs out of nonterminals: with k nonterminals, the derivation of aᵏ⁺¹bᵏ⁺¹ must revisit some nonterminal twice in the a-phase, and the segment between the two visits can be pumped, producing strings outside the language. This is the counting argument that Pumping Lemmas, Marked Positions, and the Limits of Counting Arguments formalises.

Two constructions are worth knowing because they show how the class behaves under composition:

Reversal. If L has a right-linear grammar, the reverse language Lᴿ has a left-linear grammar obtained by reversing every right-hand side. Rule A → aB becomes A → Ba. The derivation of w in G, read backwards, is a derivation of wᴿ in the reversed grammar. Left-linear grammars therefore generate exactly the reverses of right-linear languages, which is the regular languages again, since the class is closed under reversal. Orientation alone changes nothing.

Union and concatenation. A right-linear grammar for L₁ ∪ L₂ is formed by taking disjoint nonterminal sets and adding S → α for each rule S₁ → α, plus S → α for each rule S₂ → α, with fresh S. Concatenation requires an ε-rule from each accepting nonterminal of the first grammar into the start of the second, which is why ε-productions are usually permitted in the definition even though they can be eliminated. Both constructions increase the grammar size by a constant factor, matching the corresponding automaton constructions.

Mixing orientations escapes the class

Allowing both A → aB and A → Ba in one grammar is a strictly larger formalism. The smallest witness uses three nonterminals:

S → aA
A → Sb | b
S → ε

Derive a string. From S, apply S → aA, then A → Sb, then S → aA again, and so on: each round emits an a on the left and a b on the right. The derivation S ⇒ aA ⇒ aSb ⇒ aaAb ⇒ aaSbb ⇒ … produces aⁿbⁿ for every n ≥ 1, with S → ε closing the derivation at the symmetric point. That language is not regular.

The mechanism is that the two orientations place the recursive nonterminal at opposite ends, so one rule can extend the string on the left while another extends it on the right. The derivation is no longer a left-to-right scan; it builds the string from both ends inward. Equivalently, the grammar now has a stack-like discipline even though each rule is linear. Such grammars are sometimes called linear grammars, and they generate a proper subclass of the context-free languages that properly contains the regular languages. Linear grammars still cannot generate {aⁿbⁿcⁿ}, and the class sits strictly between types 2 and 3 of the hierarchy described in The Chomsky Hierarchy as a Ladder of Memory.

The practical lesson is that “linear” in a grammar does not mean “regular”. The orientation matters, and a parser generator that accepts arbitrary linear rules must handle a class larger than the one its finite-state front end can recognise.

Determinism, ambiguity, and the exponential in between

A regular grammar is ambiguous when two distinct derivations produce the same string, which happens exactly when the corresponding automaton has two accepting paths on that string. Ambiguity in a regular grammar is therefore decidable by the standard product construction on pairs of states, which searches for a string with two distinct accepting paths. Unlike the context-free case, no undecidability arises.

Determinisation is where size explodes. Converting a nondeterministic automaton with n states to a deterministic one can require 2ⁿ states, and the bound is tight for alphabets of size 2 or more: the language of binary strings whose nth symbol from the end is a 1 has an (n+1)-state NFA and a 2ⁿ-state minimal DFA. In grammar terms, a right-linear grammar with n nonterminals may need 2ⁿ nonterminals after conversion to a form whose derivations are deterministic, which is one reason regular expressions are compiled to nondeterministic automata and simulated rather than determinised.

A minimal deterministic automaton for a regular language is unique up to isomorphism, and its state count is the number of distinct right quotients of the language: states correspond to equivalence classes of strings under the relation u ≡ v iff for all w, uw ∈ L exactly when vw ∈ L. This Myhill–Nerode characterisation turns “is this language regular” into “does this relation have finitely many classes”, and it gives a decision procedure for minimality. It also gives the cleanest proof that aⁿbⁿ is not regular: the strings aᵏ for k ≥ 0 are pairwise inequivalent, so the quotient set is infinite.

Recognising a right-linear derivation in code

The grammar-to-automaton correspondence is short enough to write directly. This recogniser interprets a right-linear grammar as a nondeterministic transition table and explores all live states in parallel:

FINAL = '<final>'          # implicit accepting nonterminal with an epsilon rule

def accepts(grammar, start, word):
    """Right-linear grammar as {A: set of (terminal, next) pairs}, with a rule
    A -> a written as (a, FINAL). Returns True if some derivation derives
    exactly `word`. Implements lazy subset construction: one round per input
    symbol, all live nonterminals tracked in a set."""
    eps = {FINAL} | {A for A, rules in grammar.items() if () in rules}
    current = {start}
    for ch in word:
        nxt = set()
        for nt in current:
            for rule in grammar.get(nt, ()):
                if len(rule) == 2 and rule[0] == ch:
                    nxt.add(rule[1])
        current = nxt
        if not current:
            return False       # every path died before consuming all input
    return any(nt in eps for nt in current)

The state set is the subset construction performed lazily, so the code runs in time O(|w| · |V| · |R|) with no determinisation step and no exponential in memory beyond the set of reachable nonterminals. The eps set is computed once: a derivation is complete when the input is exhausted and the surviving nonterminal derives the empty string, which for a pure right-linear grammar means it has an explicit ε-rule. A grammar with a cycle of ε-rules would need a transitive closure over them; eliminating ε-productions first is easier, and it is also an early stage of the normal form in Chomsky Normal Form and the CYK Table.

The right-linear grammar is the weakest member of the Chomsky hierarchy and the one whose operational reading is least metaphorical: it is a finite-state machine with a syntax. Every extension of the rule shape — a second nonterminal on the right, a nonterminal on the left, a context on the left — moves the grammar to a strictly more expressive class and takes away a decision procedure somewhere. The hierarchy is, in that sense, a catalogue of exactly which extensions cost which theorems.