Right Linear Grammar

Understand right linear grammars — the grammar form that generates regular languages — where every production places the non-terminal at the right end, mirroring the structure of a finite automaton.

Definition

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

Form	Meaning
A → aB	Terminal a on the left, non-terminal B on the right
A → a	Just a single terminal (or any string of terminals)
A → ε	The empty string

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

Example

Allowed:

S → aS ← non-terminal S is on the RIGHT ✓

S → bA ← non-terminal A is on the RIGHT ✓

A → b ← no non-terminal on RHS ✓

A → ε ← empty production ✓

NOT allowed:

S → Sa ← non-terminal S is on the LEFT ✗

S → aBc ← non-terminal B is in the MIDDLE ✗

S → AB ← two non-terminals ✗

Right linear grammars generate exactly the regular languages — the same languages recognised by Deterministic and Nondeterministic Finite Automata (DFA/NFA).

Example 1 — Strings of a's Ending in b

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

These are strings of zero or more a's, followed by exactly one b.

Right Linear Grammar:

Example

G: S → aS | b

S → aS : consume one 'a', then continue with S on the right
S → b : stop by producing 'b', no more non-terminals

Derivation of "aab":

Example

Step Sentential Form Rule Applied

──── ───────────────── ──────────────

0 S

1 aS S → aS

2 aaS S → aS

3 aab S → b

The grammar "reads left to right" — each step adds one character to the left and moves the non-terminal to the right. This directly mirrors how a DFA processes input: it reads one symbol, changes state, reads the next symbol, changes state, and so on.

Equivalent NFA:

Example

States: { S, ACCEPT }

Input: { a, b }

S --a--> S (loop: keep reading a's)

S --b--> ACCEPT (move to accepting state on b)

The NFA and the grammar describe exactly the same language.

Example 2 — Binary Strings Ending in 01

Language: L = { w ∈ {0,1}* | w ends with "01" } Examples: 01, 001, 101, 0101, 1001, ...

Right Linear Grammar:

Example

G: S → 0S | 1S | 0A

A → 1B

B → ε

S handles any prefix of 0s and 1s
S → 0A means "we just read a 0 — now check if the next is a 1"
A → 1B means "we read the 1 — the string now ends in 01"
B → ε means "done — accept"

Derivation of "1001":

Example

Step Sentential Form Rule Applied

──── ───────────────── ──────────────

0 S

1 1S S → 1S

2 10S S → 0S (note: not 0A yet)

3 100A S → 0A

4 1001B A → 1B

5 1001 B → ε

Simplified equivalent grammar (same language, fewer states):

Example

S → 0S | 1S | 01

S → 01 acts as the base case when the entire suffix is just "01".

Connection to Finite Automata

Right linear grammars and finite automata (DFA/NFA) are two notations for the same thing. You can convert between them mechanically.

Grammar → NFA

For each non-terminal A, create a state named A. For each production:

A → aB → state A transitions on input 'a' to state B
A → a → state A transitions on input 'a' to the accepting state
A → ε → state A is an accepting state

Example

Grammar: NFA:

S → aS | b

a b

S ──────> S ──────> [FINAL]

NFA → Grammar

For each state q, create a non-terminal Q. For each transition:

q --a--> r → Q → aR
q --a--> accepting → Q → a
q is accepting → Q → ε

The start state's non-terminal becomes the start symbol S.

Why This Matters in Compilers

The lexer (scanner) in a compiler is implemented as a DFA. The tokens it recognises — identifiers, numbers, operators, keywords — are all described by regular expressions, which are equivalent to right linear grammars.

Example

Regular Expression Right Linear Grammar

───────────────────── ──────────────────────────────────────

[a-z][a-z0-9]* S → aA | bA | ... | zA

(identifier rule) A → aA | bA | 0A | ... | 9A | ε

Understanding right linear grammars is the theoretical foundation for understanding how lexers work.

Right vs Left Linear — A First Comparison

There are two types of linear grammars, and both generate exactly the regular languages:

Feature	Right Linear	Left Linear
Non-terminal position	At the right end: A → aB	At the left end: A → Ba
Derivation direction	Builds string left to right	Builds string right to left
Corresponds to	NFA reading input left-to-right	NFA reading input right-to-left
Same language class?	Yes — both generate regular languages	Yes

Example — same language, both styles:

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

Example

Right linear: Left linear:

S → aS | b S → Ab

A → Aa | ε

Both grammars generate {b, ab, aab, aaab, ...}.

The key insight: the direction of the non-terminal in the production rule determines whether the grammar is right-linear or left-linear, but the expressive power is identical.

The next topic covers left linear grammars in detail.

Definition

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

Form	Meaning
A → aB	Terminal a on the left, non-terminal B on the right
A → a	Just a single terminal (or any string of terminals)
A → ε	The empty string

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

Example

Allowed:

S → aS ← non-terminal S is on the RIGHT ✓

S → bA ← non-terminal A is on the RIGHT ✓

A → b ← no non-terminal on RHS ✓

A → ε ← empty production ✓

NOT allowed:

S → Sa ← non-terminal S is on the LEFT ✗

S → aBc ← non-terminal B is in the MIDDLE ✗

S → AB ← two non-terminals ✗

Right linear grammars generate exactly the regular languages — the same languages recognised by Deterministic and Nondeterministic Finite Automata (DFA/NFA).

Example 1 — Strings of a's Ending in b

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

These are strings of zero or more a's, followed by exactly one b.

Right Linear Grammar:

Example

G: S → aS | b

S → aS : consume one 'a', then continue with S on the right
S → b : stop by producing 'b', no more non-terminals

Derivation of "aab":

Example

Step Sentential Form Rule Applied

──── ───────────────── ──────────────

0 S

1 aS S → aS

2 aaS S → aS

3 aab S → b

Equivalent NFA:

Example

States: { S, ACCEPT }

Input: { a, b }

S --a--> S (loop: keep reading a's)

S --b--> ACCEPT (move to accepting state on b)

The NFA and the grammar describe exactly the same language.

Example 2 — Binary Strings Ending in 01

Language: L = { w ∈ {0,1}* | w ends with "01" } Examples: 01, 001, 101, 0101, 1001, ...

Right Linear Grammar:

Example

G: S → 0S | 1S | 0A

A → 1B

B → ε

S handles any prefix of 0s and 1s
S → 0A means "we just read a 0 — now check if the next is a 1"
A → 1B means "we read the 1 — the string now ends in 01"
B → ε means "done — accept"

Derivation of "1001":

Example

Step Sentential Form Rule Applied

──── ───────────────── ──────────────

0 S

1 1S S → 1S

2 10S S → 0S (note: not 0A yet)

3 100A S → 0A

4 1001B A → 1B

5 1001 B → ε

Simplified equivalent grammar (same language, fewer states):

Example

S → 0S | 1S | 01

S → 01 acts as the base case when the entire suffix is just "01".

Connection to Finite Automata

Right linear grammars and finite automata (DFA/NFA) are two notations for the same thing. You can convert between them mechanically.

Grammar → NFA

For each non-terminal A, create a state named A. For each production:

A → aB → state A transitions on input 'a' to state B
A → a → state A transitions on input 'a' to the accepting state
A → ε → state A is an accepting state

Example

Grammar: NFA:

S → aS | b

a b

S ──────> S ──────> [FINAL]

NFA → Grammar

For each state q, create a non-terminal Q. For each transition:

q --a--> r → Q → aR
q --a--> accepting → Q → a
q is accepting → Q → ε

The start state's non-terminal becomes the start symbol S.

Why This Matters in Compilers

Example

Regular Expression Right Linear Grammar

───────────────────── ──────────────────────────────────────

[a-z][a-z0-9]* S → aA | bA | ... | zA

(identifier rule) A → aA | bA | 0A | ... | 9A | ε

Understanding right linear grammars is the theoretical foundation for understanding how lexers work.

Right vs Left Linear — A First Comparison

There are two types of linear grammars, and both generate exactly the regular languages:

Feature	Right Linear	Left Linear
Non-terminal position	At the right end: A → aB	At the left end: A → Ba
Derivation direction	Builds string left to right	Builds string right to left
Corresponds to	NFA reading input left-to-right	NFA reading input right-to-left
Same language class?	Yes — both generate regular languages	Yes

Example — same language, both styles:

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

Example

Right linear: Left linear:

S → aS | b S → Ab

A → Aa | ε

Both grammars generate {b, ab, aab, aaab, ...}.

The key insight: the direction of the non-terminal in the production rule determines whether the grammar is right-linear or left-linear, but the expressive power is identical.

The next topic covers left linear grammars in detail.