Grammars — Basics & Regular Grammars¶

What Is a Grammar?¶

A grammar G is a formal device for generating the strings of a language. It specifies a finite set of production rules that can be applied repeatedly, starting from a designated start symbol, to derive any string in the language.

Formal Definition¶

A grammar is a 4-tuple:

G = (V, Σ, R, S)

Component	Description
V	Finite set of variables (also called non-terminals). These are intermediate symbols used during derivation — they never appear in the final string.
Σ	Finite set of terminals (the alphabet). These are the actual symbols of the language. V ∩ Σ = ∅.
R	Finite set of production rules of the form α → β, where α, β ∈ (V ∪ Σ)*.
S	Start symbol: S ∈ V. Every derivation begins here.

A derivation is a sequence of rule applications that transforms S into a string of terminals:

S ⟹ α₁ ⟹ α₂ ⟹ … ⟹ w    (w ∈ Σ*)

The language generated by G, written L(G), is the set of all terminal strings derivable from S:

L(G) = { w ∈ Σ* | S ⟹* w }

---

Regular Grammars¶

A regular grammar is a grammar in which every production rule has a single non-terminal on the left-hand side, and the right-hand side has a restricted form:

• At most one non-terminal, which appears only at one end (left or right) of the right-hand side.
• No nesting of non-terminals within each other.

There are two equivalent styles:

Right-Linear Grammar¶

Every rule has the form A → wB or A → w, where A, B ∈ V and w ∈ Σ* (a string of terminals, possibly empty).

The non-terminal (if present) is always at the right end.

Left-Linear Grammar¶

Every rule has the form A → Bw or A → w, where A, B ∈ V and w ∈ Σ*.

The non-terminal (if present) is always at the left end.

Theorem: Both right-linear and left-linear grammars generate exactly the class of regular languages. They are interconvertible.

---

Regular Grammar Examples¶

Example 1: L = {aⁿb | n ≥ 0}¶

Right-Linear:

S → aS | b

Derivation of aab: S ⟹ aS ⟹ aaS ⟹ aab.

Left-Linear:

S → Ab
A → Aa | ε

Derivation of aab: S ⟹ Ab ⟹ Aab ⟹ Aaab ⟹ aab — wait, we apply left-linear differently: S ⟹ Ab ⟹ Aab ⟹ εaab = aab (applying A → ε last).

Example 2: L = { w ∈ {0,1}* | w ends in 01 }¶

Right-Linear:

S → 0S | 1S | 0A
A → 1

Left-Linear:

S → A1
A → B0
B → B0 | B1 | ε

Example 3: L = { w ∈ {0,1}* | w has an even number of 0s }¶

Right-Linear:

S → 0A | 1S | ε
A → 0S | 1A

Left-Linear:

S → A0 | S1 | ε
A → S0 | A1

---

Converting Between Left-Linear and Right-Linear¶

Both styles generate the same language. To convert between them, the standard approach is:

1. Build a finite automaton from the given grammar.
2. Re-derive the grammar of the other style from that FA.

LL → RL Conversion Rules¶

1. Create a new start state S_new.
2. Non-terminals of the LL grammar become states of the FA.
3. The original start symbol S becomes a final (accept) state of the FA.
4. For each rule A → Ba, add transition B → A on input a (i.e., δ(B, a) = A).
5. For each rule A → a or A → ε, add transition S_new → A on input a or ε.
6. Re-derive the RL grammar from the FA:
7. S_new becomes the new start symbol.
8. For each transition A → B on input a, add rule A → aB.
9. Add S → ε (the old accept state becomes nullable).

RL → LL Conversion Rules¶

1. Non-terminals become states of the FA.
2. For each rule A → aB, add transition δ(A, a) = B.
3. For each terminal rule A → a or A → ε, create a new final state F and add transition δ(A, a) = F or δ(A, ε) = F.
4. Re-derive the LL grammar from the FA:
5. F becomes the new start symbol.
6. For each transition δ(A, a) = B, add rule B → Aa.
7. Add S → ε.

Worked Example: LL → RL¶

Given LL grammar:

S → A1
A → B0
B → B0 | B1 | ε

Step 1: Build the FA.

States: {S_new, S, A, B}. Final state: S.

From the rules: - A → B0 → transition δ(B, 0) = A - S → A1 → transition δ(A, 1) = S - B → B0 → transition δ(B, 0) = B (but we already have δ(B,0) = A; NFAs allow both) - B → B1 → transition δ(B, 1) = B - B → ε → S_new →ε B

FA table:

State	0	1	ε
→ S_new	∅	∅	{B}
* S	∅	∅	∅
A	∅	{S}	∅
B	{A, B}	{B}	∅

Step 2: Re-derive the RL grammar.

• Start symbol: S_new
• S_new → εB simplifies to S_new → B (or since ε-transition, S_new effectively starts at B)
• B → 0B | 1B | 0A
• A → 1S
• S → ε

Resulting RL grammar:

S_new → B          (via ε-transition to B)
B → 0B | 1B | 0A
A → 1S
S → ε

This accepts the same language as the original LL grammar.