Left Linear and Right Linear Grammars and Conversions

 

Left-Linear Grammar (LLG)

• In a left-linear grammar, every production rule has the nonterminal on the left side of the string.

• The general forms are:

$$A \;\to\; Bx \quad \text{or} \quad A \;\to\; x$$

where:

• $A, B$ = nonterminals

• $x$ = terminal string (possibly empty)

Example:

$$S \;\to\; A b, \quad A \;\to\; a$$

This grammar generates "ab".

---

Right-Linear Grammar (RLG)

• In a right-linear grammar, every production rule has the nonterminal on the right side of the string.

• The general forms are:

$$A \;\to\; xB \quad \text{or} \quad A \;\to\; x$$

where:

• $A, B$ = nonterminals

• $x$ = terminal string (possibly empty)

Example:

$$S \;\to\; aA, \quad A \;\to\; b$$

This grammar also generates "ab".

---

Difference Between Left-Linear and Right-Linear

• Right-linear grammars generate strings by expanding towards the right.

• Left-linear grammars generate strings by expanding towards the left.

• Both describe exactly the class of regular languages ✅.

---

🔹 Converting Between Them

Suppose we have a right-linear grammar:

$$S \;\to\; aA, \quad A \;\to\; b$$

Step 1: Recognize that it generates "ab".

Step 2: To convert to left-linear, we "mirror" the structure:

$$S \;\to\; A b, \quad A \;\to\; a$$

Step 3: Both grammars generate the same language, but derivations work in different directions.

---

🔹  General Conversion (Idea)

👉 To convert Right-Linear → Left-Linear (or vice versa):

1. Take the finite automaton (FA) corresponding to the grammar.
   (Since every regular grammar corresponds to an FA.)

2. Reverse the FA transitions.

3. Construct the grammar again, but now in the other form (LLG or RLG).

This works because reversing a regular grammar gives the mirror language, and both left- and right-linear grammars describe regular languages.

---

✅ Key Point for Students:

• Right-linear grammars are easier to read left to right.

• Left-linear grammars are easier to read right to left.

• But both describe regular languages, and we can always convert by going through a finite automaton representation.

Example

The LLG for a grammar is given find the  RLG

B ⇢ Ba/Bb/Ab
A ⇢ ∈

Step 1: Convert the LLG into FA 

Step 2: Reverse the FA(i.e. initial state is converted into final state and convert final state to initial state and reverse all edges)

Step 3: Write RLG corresponding to reversed FA.

A ⇢ bB
B ⇢ aB/bB/∈