Unit III: Context-Free Grammars
Unit III: Context-Free Grammars, Regular Grammars & Normal Forms
Complete Exam Preparation Notes with Examples, Proofs & Shortcuts
1. Context-Free Grammar (CFG) – Definition
A CFG is a 4-tuple G = (V, Σ, P, S) where:
- V → finite set of variables (non-terminals)
- Σ → finite set of terminals
- P → finite set of productions of form A → α (A ∈ V, α ∈ (V ∪ Σ)*)
- S ∈ V → start symbol
Example: Grammar for balanced parentheses
S → SS | (S) | ε
Generates: ε, (), (()), ()(), (()()), etc.
S → SS | (S) | ε
Generates: ε, (), (()), ()(), (()()), etc.
2. Derivations, Parse Trees & Ambiguity
| Concept | Explanation | Example |
|---|---|---|
| Leftmost Derivation | Always expand leftmost non-terminal | S ⇒ (S) ⇒ (SS) ⇒ ... |
| Rightmost Derivation | Always expand rightmost non-terminal | Used in LR parsing |
| Parse Tree (Derivation Tree) | Tree showing structure of derivation | Root = S, leaves = terminals |
| Ambiguous Grammar | String has ≥2 leftmost derivations OR ≥2 parse trees | E → E+E | E*E | id → "id + id * id" has 2 trees |
| Inherently Ambiguous Language | No unambiguous grammar exists | {aⁿbⁿcᵐ | n,m≥0} ∪ {aⁿbᵐcᵐ | n,m≥0} |
3. Regular Grammars (Type-3)
A grammar is regular if all productions are of one of these two forms:
- Right Linear: A → aB or A → a or A → ε (a ∈ Σ, A,B ∈ V)
- Left Linear: A → Ba or A → a or A → ε
Every Regular Grammar generates a Regular Language
Every Regular Language has a Regular Grammar
Every Regular Language has a Regular Grammar
Conversion: FA ⇄ Regular Grammar
| Direction | Method |
|---|---|
| DFA → Right Linear Grammar | States become variables δ(qᵢ, a) = qⱼ → Qᵢ → a Qⱼ If qᵢ final → Qᵢ → ε or Qᵢ → a |
| Right Linear Grammar → NFA | Variables → states A → aB → transition A --a→ B A → a → transition A --a→ new final state |
DFA → Grammar Example
DFA: q0 --0→ q0, q0 --1→ q1, q1 --1→ q2, q2 is final
Grammar:
Q0 → 0 Q0 | 1 Q1
Q1 → 1 Q2
Q2 → ε
DFA: q0 --0→ q0, q0 --1→ q1, q1 --1→ q2, q2 is final
Grammar:
Q0 → 0 Q0 | 1 Q1
Q1 → 1 Q2
Q2 → ε
4. Simplification of CFG (Must for Exam)
Steps to Simplify (Remove in this order):
- Eliminate ε-productions (except if S → ε is only way to get ε)
- Eliminate unit productions (A → B)
- Eliminate useless symbols (not reachable or not generating terminals)
- Remove unreachable & non-productive symbols
5. Normal Forms (Most Important for Exams)
A. Chomsky Normal Form (CNF)
A CFG is in CNF if every production is of form:
A → BC or A → a or S → ε (only if ε ∈ L(G))
(B, C are non-terminals, a is terminal)
A → BC or A → a or S → ε (only if ε ∈ L(G))
(B, C are non-terminals, a is terminal)
Conversion Steps to CNF (Standard Algorithm – 8 Marks Question)
- Remove ε, unit, useless productions
- Replace terminals in long rules: A → aBc → A → XBc, X → a
- Break rules longer than 2: A → BCDE → A → BF, F → CD, C → BE, etc.
S → aSb | ε
→ After CNF:
S → AB | ε
A → a
B → Sb
Wait! Still not CNF → continue...
Final CNF:
S → AB | ε
A → a
B → SC
C → b
→ After CNF:
S → AB | ε
A → a
B → Sb
Wait! Still not CNF → continue...
Final CNF:
S → AB | ε
A → a
B → SC
C → b
B. Greibach Normal Form (GNF)
A CFG is in GNF if every production is:
A → aα where a ∈ Σ, α ∈ V* (starts with terminal)
A → aα where a ∈ Σ, α ∈ V* (starts with terminal)
Key Points for Exam
- Every CFL (without ε) has a GNF
- Useful for top-down parsing
- Conversion is longer but asked in exams
6. Chomsky Hierarchy (Must Memorize)
| Type | Grammar | Language | Automaton |
|---|---|---|---|
| Type-0 | Unrestricted | Recursively Enumerable | Turing Machine |
| Type-1 | Context-Sensitive | Context-Sensitive | Linear Bounded Automaton |
| Type-2 | Context-Free | Context-Free | Pushdown Automaton |
| Type-3 | Regular | Regular | Finite Automaton |
7. Programming / Exam-Oriented Problems on CFG Properties
- Check if grammar is ambiguous
- Remove left recursion
- Convert to CNF / GNF step-by-step
- Find language generated by grammar
- Construct grammar for {aⁿbⁿ | n≥0}, {wwʳ}, palindromes, etc.
- Prove two grammars generate same language
Most Important Exam Questions – Unit III
- Convert given FA → Regular Grammar and vice-versa (8 marks)
- Eliminate ε, unit, useless productions step-by-step
- Convert CFG to CNF (full steps) (10–12 marks)
- Prove given grammar is ambiguous + remove ambiguity
- Construct CFG for regular & non-regular CFLs
- Remove left recursion and do left factoring
- Explain Chomsky Hierarchy with examples
- Prove {aⁿbⁿcⁿ} is not context-free using Pumping Lemma for CFLs (Unit IV, but sometimes asked)
Quick Revision One-Liners
- Right-linear grammar ⇔ Regular language
- CNF: only A→BC or A→a
- GNF: every rule starts with terminal
- Ambiguity is grammar property, not language (unless inherently ambiguous)
- Every regular language has infinitely many grammars
- S → ε allowed in CNF only if ε is in language
You are now FULLY PREPARED for Unit III!
Practice 5 CNF conversions + 3 ambiguity + 3 FA⇄Grammar → 100% Marks Guaranteed!
Practice 5 CNF conversions + 3 ambiguity + 3 FA⇄Grammar → 100% Marks Guaranteed!