Linear and Non Linear Context Free Grammers

 

📌 Linear Context-Free Grammar (Linear CFG)

A linear grammar is a context-free grammar where at most one variable (non-terminal) appears on the right-hand side of every production.

Formally:
Each production has the form

$$A \to u B v \quad \text{or} \quad A \to w$$

where:

• $A, B$ are variables (nonterminals),

• $u, v, w \in \Sigma^*$(strings of terminals),

• and at most one variable appears in the right-hand side.

👉 In other words:

• Right-hand side can contain zero or one variable.

• If there is a variable, it can appear anywhere in the string (beginning, middle, or end).

Example of Linear CFG:

S → aSb | ab

• Rule S → aSb has one variable S in the middle → allowed.

• Rule S → ab has no variable → allowed.

This grammar generates the language { a^n b^n | n ≥ 1 }, which is context-free and linear.

Another example:

A → aA | A b | ab

• Always at most one nonterminal on RHS → linear.

---

📌 Non-Linear Context-Free Grammar (Non-Linear CFG)

A grammar is non-linear if any rule has more than one variable on the right-hand side.

Example:

S → AB
A → aA | a
B → bB | b

• Rule S → AB has two variables (A and B) → ❌ not linear.

This grammar generates { a^n b^m | n, m ≥ 1 }, which is context-free but non-linear.

---

📌 Key Difference

• Linear CFG → At most one variable per RHS → languages are called linear languages (subset of CFLs).

• Non-Linear CFG → RHS may contain two or more variables → can generate more complex CFLs.

---

📌 Significance

• Every linear language is a context-free language (CFL), but not all CFLs are linear.

• Linear languages are easier to parse (some can even be parsed in polynomial time similar to regular languages).

• Example: a^n b^n is linear, but { a^n b^n c^n } requires non-linear CFG.

---

✅ So:

• Linear CFG: RHS has ≤ 1 variable.

• Non-linear CFG: RHS can have ≥ 2 variables