Left Linear Grammar

A left linear grammar (also called a left regular grammar) is a grammar G = (V, T, P, S) where every production rule has one of these three forms:

The defining feature: the non-terminal always appears at the left end of the right-hand side (if it appears at all).

Like right linear grammars, left linear grammars also generate exactly the regular languages. The two types of grammars are equally powerful — they differ only in the direction from which they build strings.

Language: L = {aⁿb | n ≥ 0} = {b, ab, aab, aaab, ...}

Left Linear Grammar:

• A → ε : A can be the empty string (generating zero a's)
• A → Aa : A generates one more 'a' on the right (builds up a string of a's)
• S → Ab : Append 'b' to whatever A generates

Derivation of "aab":

Why does this work?

A → Aa | ε makes A generate any string in {aⁿ | n ≥ 0}:

• A → ε → A = "" (zero a's)
• A → Aa → εa → A = "a" (one a)
• A → Aa → Aaa → εaa → A = "aa" (two a's)

Then S → Ab appends a 'b', giving {aⁿb | n ≥ 0} ✓

Notice how the grammar builds from the inside out, growing the string of a's to the right of A, then finally removing A when done. This is the opposite of right linear grammars, which build left to right one step at a time.

Language: L = {ab · w | w ∈ {a, b}*} — strings that start with "ab" Examples: ab, aba, abb, abaa, abab, abba, ...

Left Linear Grammar:

Hmm, this is getting complex. Let me use a cleaner approach.

Because left-linear grammars build strings from right to left (the non-terminal is on the left side), it is often easier to think of them as "suffix grammars" — they describe what comes at the END of the derivation and build leftward.

Cleaner grammar for ab · {a,b}*:

Derivation of "abba":

Reading the derivation: The rightmost characters are appended first. S reads right-to-left over the string. A marks the point where the prefix "ab" is finally produced.

The same regular language can always be expressed by both a left linear grammar and a right linear grammar. The difference is purely structural — the direction from which the non-terminal "moves" through the string.

Language: L = {aⁿb | n ≥ 0}

Language: L = {a, b}* (all strings over {a, b}, including ε)

Formal Comparison Table

The Conversion Trick

Every left linear grammar can be converted to an equivalent right linear grammar by reversing the language:

1. Replace each left linear rule A → Ba with A' → aB' (mirror the rule)
2. Reverse the roles of start and accepting states

This works because reversing a regular language always gives another regular language.

Both right linear and left linear grammars are collectively called regular grammars. They sit at the bottom of the Chomsky Hierarchy (Type 3) and are the least powerful class of grammars.

Why Regular Grammars Matter in Compiler Design

The lexical analysis (scanner/tokeniser) phase of a compiler uses regular grammars:

The regular grammar describes the structure of each token type. The compiler tool lex (or flex) takes these descriptions and automatically builds the DFA that recognises them.

Key Takeaway

Regular grammars are simple, fast, and sufficient for lexical analysis. More power (context-free, context-sensitive) is needed for parsing full programs.