📘 PAPER 1: THEORY OF COMPUTATION (MCA546) UNIT -3 Context Free Grammars (CFG) (university of allahabad)

🔴 UNIT 3: Context Free Grammars (CFG)

(EXTREMELY IMPORTANT – Long answers + conversions often asked)

---

1️⃣ Context Free Grammar (CFG)

Definition

A Context Free Grammar is a grammar in which each production rule has a single non-terminal on the left-hand side.

Formal Definition

A CFG is a 4-tuple:

G = (V, Σ, P, S)

Where:

• V → Set of non-terminals

• Σ → Set of terminals

• P → Production rules

• S → Start symbol

---

Form of Productions

A → α
Where:

• A ∈ V

• α ∈ (V ∪ Σ)*

---

Example

Grammar for L = { aⁿbⁿ | n ≥ 1 }

Productions:

• S → aSb

• S → ab

---

2️⃣ Derivation in CFG

Derivation

Process of generating strings from the start symbol using production rules.

---

Types of Derivation

Leftmost Derivation

• Always expand the leftmost non-terminal

Rightmost Derivation

• Always expand the rightmost non-terminal

---

Example

S → aSb → aab b

---

3️⃣ Derivation Trees (Parse Trees)

Definition

A derivation tree (or parse tree) is a tree representation of how a string is generated in a CFG.

---

Properties

• Root → Start symbol

• Internal nodes → Non-terminals

• Leaves → Terminals

• Reading leaves left to right gives the string

---

Importance

• Shows structure of language

• Used in compilers

• Common exam question

---

4️⃣ Ambiguity in CFG

Ambiguous Grammar

A grammar is ambiguous if a string has more than one parse tree.

---

Example

Grammar:
E → E + E | E * E | id

Expression: id + id * id

➡ Two different parse trees possible

---

Key Point

• Some languages are inherently ambiguous

• Ambiguity is undesirable in compilers

---

5️⃣ Simplification of Context Free Grammars

Simplification means removing unnecessary productions without changing the language.

---

Steps of Simplification

(a) Removal of ε-productions

Productions of the form:
A → ε

---

(b) Removal of Unit Productions

Productions of the form:
A → B

---

(c) Removal of Useless Symbols

• Non-generating symbols

• Unreachable symbols

---

Result

Simplified grammar that generates the same language

---

6️⃣ Chomsky Normal Form (CNF)

Definition

A CFG is in Chomsky Normal Form if all productions are of the form:

• A → BC

• A → a

Where:

• A, B, C ∈ V

• a ∈ Σ

---

Special Rule

S → ε allowed if ε ∈ L

---

Steps to Convert CFG to CNF

1. Remove ε-productions

2. Remove unit productions

3. Remove useless symbols

4. Convert long RHS into binary form

5. Replace terminals in long productions

---

Importance

• Used in parsing algorithms

• Asked as long conversion question

---

7️⃣ Greibach Normal Form (GNF)

Definition

A CFG is in Greibach Normal Form if every production is of the form:

A → aα

Where:

• a ∈ Σ

• α ∈ V*

---

Characteristics

• Right-hand side starts with a terminal

• No left recursion

---

Importance

• Useful in top-down parsing

• Ensures derivations consume input symbols

---

8️⃣ Decision Algorithms for CFG

Decidable Problems

1. Membership problem
   Given string w, determine whether w ∈ L(G)

2. Emptiness problem
   Determine whether L(G) = ∅

3. Finiteness problem
   Check if L(G) is finite

---

Undecidable Problem

• Equivalence of two CFGs

---

🔑 CFG vs Regular Grammar

CFG	Regular Grammar
More powerful	Less powerful
PDA required	FA sufficient
Supports recursion	No recursion