Chapter 14 of 34

Regular Grammars

We now have two ways to describe a regular language: machines that recognise strings (finite automata) and formulas that describe them (regular expressions). There is a third way, and it is the one that grows into the rest of this course: grammars, which generate strings by rewriting rules.

A grammar works like a recipe: "a sentence is a subject followed by a verb phrase; a subject is …". Repeatedly replacing a name by one of its definitions produces strings of the language. When the rules are restricted so that the string grows only at one end, the grammar generates exactly the regular languages.

A regular grammar is a grammar in which every production is right-linear (A → xB or A → x) or every production is left-linear (A → Bx or A → x), where A, B are variables and x is a string of terminals. Regular grammars generate exactly the regular languages.

In this chapter we define grammars just enough to work with them, convert between finite automata and right-linear and left-linear grammars in both directions, and see why mixing the two kinds breaks regularity. Every grammar in this chapter was checked by a program that generated all its strings up to length 9 and compared them with the intended language.


Grammars in Five Minutes

A grammar is a 4-tuple G = (V, T, P, S):

Part

Meaning

Convention

V

variables (non-terminals): names for sets of strings

capital letters S, A, B

T

terminals: the alphabet of the generated strings

lowercase letters, digits

P

productions (rules) of the form α → β

A → aB means "A may be replaced by aB"

S

start symbol, a member of V

usually S

A derivation starts with S and repeatedly replaces a variable using a rule, written ⇒. The language L(G) is the set of all terminal strings that can be derived from S. Several rules with the same left side are combined with |, so A → aB | b means A → aB and A → b.

Example. G: S → aS | b.

S ⇒ b
S ⇒ aS ⇒ ab
S ⇒ aS ⇒ aaS ⇒ aab
L(G) = { b, ab, aab, aaab, … } = a*b

Notice the shape of every sentential form: some terminals followed by at most one variable at the right end. That variable is the only "memory" the grammar has, just like the current state of a finite automaton. This is the whole secret of this chapter.

Grammars in general (context-free and beyond) are studied from Context-Free Grammars onwards; here we only need the linear kinds.


Right-Linear and Left-Linear Grammars

Let A, B ∈ V and x ∈ T* (a string of terminals, possibly ε).

Type

Allowed productions

Strings grow

Example

Right-linear

A → xB, A → x

to the right; the variable is at the right end

S → aS | bA, A → ε

Left-linear

A → Bx, A → x

to the left; the variable is at the left end

S → Sa | Ab, A → ε

A regular grammar is one that is entirely right-linear or entirely left-linear. In the Chomsky hierarchy, these are the Type 3 grammars.

Many books use a stricter form with exactly one terminal per rule: A → aB, A → a, plus S → ε if ε is needed (sometimes A → ε is allowed for any A). Any right-linear grammar can be put into this form by splitting long rules (shown below), so the strict and the general definitions generate the same class of languages.


Finite Automaton to Right-Linear Grammar

The correspondence is direct: states become variables, arrows become rules.

  • For every arrow p –a→ q, add the rule p → aq.

  • For every accepting state q, add q → ε.

  • The start symbol is the start state.

Variable p then generates exactly the strings that take the automaton from p to acceptance. A derivation is just a run of the machine written down step by step.

Example 1: strings ending with ab

State

a

b

→ A

B

A

B

B

C

* C

B

A

A → aB | bA
B → aB | bC
C → aB | bA | ε

Derivation of "bab", matching the run A –b→ A –a→ B –b→ C:

A ⇒ bA ⇒ baB ⇒ babC ⇒ bab

Variant without ε-rules. Instead of C → ε, add p → a for every arrow p –a→ q into an accepting state q. Here the only arrow into C is B –b→ C, so:

A → aB | bA
B → aB | bC | b
C → aB | bA

Both grammars generate exactly "ends with ab" (the program compared both with the definition on all 1023 strings of length at most 9). If the start state itself is accepting, the ε-free variant must add S → ε separately, since ε cannot be produced any other way.


Right-Linear Grammar to Finite Automaton

Reverse the recipe: variables become states, rules become arrows.

Rule

Automaton part

A → aB

arrow A –a→ B

A → a

arrow A –a→ F, where F is one new accepting state

A → ε

make A accepting

A → B (unit rule)

ε-arrow A –ε→ B

A → a1a2…akB

a chain A –a1→ X1 –a2→ … –ak→ B through k − 1 new states

A → a1a2…ak

a chain ending in F

The start state is S. The result is usually an NFA (several rules for A with the same first symbol give a choice), which you can determinise with the subset construction if needed.

Example 2: rules with long right sides

S → abS | baA | a
A → bA | ε

States: S, A, F (for S → a) and two chain states X1 (for abS) and X2 (for baA).

State

a

b

From rule

→ S

{X1, F}

{X2}

S → abS, S → a, S → baA

X1

∅

{S}

second symbol of abS

X2

{A}

∅

second symbol of baA

* A

∅

{A}

A → bA, and A → ε makes A accepting

* F

∅

∅

end of S → a

          b
     .---------.
     v         |
 → (S) --a--> (X1)          (S) --a--> ((F))
     |
     '--b--> (X2) --a--> ((A)) ↻ b

Reading the machine (or the grammar): any number of ab blocks, then either a single a, or ba followed by any number of b's. So L = (ab)*(a + bab*). The grammar, the NFA and this regular expression all agree on every string up to length 9.


Left-Linear Grammars

A left-linear grammar builds the string from right to left: in S ⇒ Ab ⇒ Bab ⇒ …, the last symbol is produced first. So it is natural to read the variables the other way: variable A stands for the strings that take the machine from the start state to A.

Example 3: "ends with ab" with a left-linear grammar

S → Ab               (the last symbol is b, and before it comes …)
A → Ba | a           (… an a, and before that anything, possibly nothing)
B → Ba | Bb | a | b  (B = any non-empty string)

Derivation of "bab": S ⇒ Ab ⇒ Bab ⇒ bab.

Left-linear grammar to finite automaton (direct method)

  • Create a new start state Q0. Each variable is a state. The start symbol S is the accepting state.

  • For A → Ba: arrow B –a→ A (first reach B, then read a to reach A).

  • For A → a: arrow Q0 –a→ A. For A → ε: arrow Q0 –ε→ A. Long right sides become chains as before.

For Example 3:

State

a

b

From rule

→ Q0

{A, B}

{B}

A → a, B → a, B → b

A

∅

{S}

S → Ab

B

{A, B}

{B}

A → Ba, B → Ba, B → Bb

* S

∅

∅

start symbol is accepting

This NFA accepts exactly "ends with ab" (checked).

The reversal method (the one many textbooks use)

Reversing the right side of every rule of a left-linear grammar gives a right-linear grammar for the reverse language LR. So:

  1. Reverse every right side: S → bA, A → aB | a, B → aB | bB | a | b. This right-linear grammar generates LR = strings starting with ba.

  2. Build the finite automaton for LR as in the previous section.

  3. Reverse that automaton (reverse every arrow, swap start and accepting states, adding a new start with ε-arrows if there are several accepting states). The result accepts L.

Both methods give the same language; the direct method saves two reversals.

Finite automaton to left-linear grammar

Use the "from the start to A" reading:

  • For every arrow p –a→ q, add q → pa.

  • Add q0 → ε for the start state.

  • The start symbol is the accepting state (with several accepting states, add a new S → F1 | F2 | …).

For the DFA of Example 1 (accepting state C):

C → Bb
B → Aa | Ba | Ca
A → Ab | Cb | ε

with start symbol C. This left-linear grammar generates "ends with ab" too, so right-linear and left-linear grammars generate the same class of languages, the regular languages. Converting RLG → LLG (or back) is simplest by going through the automaton.


Why You Must Not Mix Left and Right

Each kind alone is regular. But consider this grammar, which uses one right-linear rule and one left-linear rule:

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

Substituting A gives S → aSb | ε, so

L = { ε, ab, aabb, aaabbb, … } = { aⁿbⁿ : n ≥ 0 }

which is not regular (no finite automaton can count the a's; the formal proof is in Pumping Lemma for Regular Languages). A grammar whose rules have at most one variable on the right, placed anywhere, is called a linear grammar; linear grammars are more powerful than regular grammars. So "regular" requires all rules to be right-linear or all to be left-linear.


Summary of Conversions

From

To

Rule of thumb

FA

Right-linear grammar

p –a→ q gives p → aq; accepting q gives q → ε; start symbol = start state

Right-linear grammar

FA

A → aB gives A –a→ B; A → a goes to a new accepting state; A → ε makes A accepting

FA

Left-linear grammar

p –a→ q gives q → pa; start state → ε; start symbol = accepting state

Left-linear grammar

FA

A → Ba gives B –a→ A; A → a gives Q0 –a→ A; S is accepting (or use the reversal method)

Right-linear grammar

Regular expression

treat rules as equations X = PX + Q and use Arden's rule X = P*Q

The last row is a nice link with Finite Automata to Regular Expression (Arden's Theorem): for S → aS | b, the equation S = aS + b gives S = a*b immediately.


Common Mistakes

  • Mixing right-linear and left-linear rules in one grammar and calling it regular. The result can be non-regular (anbn above).

  • Forgetting accepting states when converting FA → grammar: without q → ε (or the p → a rules) the grammar cannot stop and generates nothing.

  • Forgetting ε in the ε-free variant when the start state is accepting.

  • Reading a left-linear grammar left to right. In S → Ab, the b is the last symbol of the string.

  • Reversing only the grammar in the reversal method but forgetting to reverse the automaton at the end, which gives LR instead of L.

  • Making every rule A → a go to a different new state. One shared accepting state F is enough.


GATE-Style Questions

Q1. What language does S → aS | B, B → bB | ε generate? Is the grammar regular?

a*b*. Yes, it is right-linear: S → B has the form A → xB with x = ε, which is allowed in the general definition (it becomes an ε-arrow in the automaton).

Q2. What language does the left-linear grammar S → Sa | Sb | a generate?

The leftmost symbol is produced last, by S → a. Before that, any a's and b's are added on the right. So L = a(a + b)*, strings starting with a.

Q3. Is the grammar S → aSb | ab regular? Is its language regular?

Neither. The rule S → aSb has terminals on both sides of the variable, so it is not right- or left-linear (it is linear). Its language { anbn : n ≥ 1 } is not regular.

Q4. Write a right-linear grammar for strings over {a, b} with an even number of a's.

Two states: S (even so far, accepting) and A (odd so far). S → aA | bS | ε, A → aS | bA.

Q5. A right-linear grammar in strict form (A → aB | a) has 4 variables. How many states does the NFA built from it have?

One per variable plus one new accepting state F: 5 states (fewer if no rule of the form A → a exists, since then F is not needed).

Q6. If L is generated by a left-linear grammar G, which language does the grammar obtained by reversing every right side of G generate?

The reverse language LR. The new grammar is right-linear, so LR is regular as well (this is exactly step 1 of the reversal method above).


Summary

  • A grammar G = (V, T, P, S) generates strings by rewriting variables with productions.

  • Right-linear: A → xB | x. Left-linear: A → Bx | x. A regular (Type 3) grammar uses only one of the two kinds.

  • Right-linear grammars and finite automata correspond one to one: variables ↔ states, rules ↔ arrows, A → ε ↔ accepting.

  • Left-linear grammars read the variable as "strings that lead from the start to here"; convert directly, or reverse to a right-linear grammar, build the FA and reverse it.

  • Right-linear grammars, left-linear grammars, finite automata and regular expressions all describe exactly the regular languages.

  • Mixing left- and right-linear rules can produce non-regular languages such as anbn.