UNIT IV - Context-Free Grammars

UNIT – IV- Mathematical Foundations of Computer Science & Automata

Context-Free Grammars

Syllabus: Context-Free Grammar (CFG) · Derivations and Parse Trees · Ambiguity · CFG Simplification · Chomsky Normal Form (CNF) · Greibach Normal Form (GNF) · Pumping Lemma for CFLs

1.1  Introduction

A Context-Free Grammar (CFG) is a formal grammar used to describe the syntax and structure of languages. It is widely used in compiler design, programming languages, and the study of formal languages. A CFG specifies how strings can be generated using a set of production rules.

Why “context-free”? A non-terminal can be replaced according to a production rule regardless of the symbols surrounding it (its context).

1.2  Formal Definition

A CFG is a four-tuple:             G = (V, T, P, S)

Component	Meaning	Example
V	Finite set of variables / non-terminal symbols	{S, A}
T	Finite set of terminal symbols	{a, b}
P	Finite set of production rules	S → aSb
S	Start symbol, S ∈ V	S

Terminals are the actual symbols that appear in the generated string. Non-terminals are variables that are replaced using production rules.

1.3  Production Rules

Every production has the general form:

A → α      (A ∈ V,  α ∈ (V ∪ T)^*)

The left-hand side must be exactly one non-terminal; the right-hand side α is any string of terminals and/or non-terminals, including the empty string ε.

Production	Valid CFG rule?	Reason
S → aSb	Yes	One non-terminal on the left
S → ab	Yes	Right side may be all terminals
S → aA	Yes	Mixed terminal and non-terminal
S → ε	Yes	Empty string is allowed on the right
aS → b	No	Left side has a terminal as well as a non-terminal
AB → a	No	Left side has two symbols

1.4  Language Generated by a Grammar

L(G) = { w ∈ T*  |  S ⇒* w }

It is the set of all terminal strings that can be derived from the start symbol.

1.5  Example 1 — Equal Numbers of a’s and b’s

Grammar: S → aSb | ab

This grammar generates strings with n a’s followed by n b’s, with at least one of each:

L(G) = { aⁿbⁿ | n ≥ 1 }

String	Derivation
ab	S ⇒ ab
aabb	S ⇒ aSb ⇒ aabb
aaabbb	S ⇒ aSb ⇒ aaSbb ⇒ aaabbb
aaaabbbb	S ⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaaabbbb

1.6  Example 2 — Palindromes over {a, b}

Grammar: S → aSa | bSb | a | b | ε

Rule	Purpose
S → aSa,  S → bSb	Adds the same symbol at both ends
S → a,  S → b	Odd-length palindromes (middle symbol)
S → ε	Even-length palindromes (empty middle)

Example: S ⇒ aSa ⇒ abSba ⇒ abba.

1.7  Applications of CFG

Area	Use
Compiler design	Defines the syntax of programming languages
Syntax analysis	Checks whether source code follows the grammar rules
Natural language processing	Represents grammatical structure of sentences
Expression parsing	Describes arithmetic expressions and operator structure
Pushdown automata	CFGs and pushdown automata describe exactly the context-free languages

  TOPIC 2  Derivations and Parse Trees 

2.1  Derivation

A derivation is the process of generating a string from the start symbol by repeatedly applying production rules. The symbol ⇒ represents one application of a production.

Example: For S → aSb | ab, the string aabb is derived as  S ⇒ aSb ⇒ a(ab)b ⇒ aabb.  Hence aabb ∈ L(G).

22.2  Types of Derivation

Type	Rule	Symbol used
Leftmost derivation (LMD)	The leftmost non-terminal is replaced first at every step	⇒lm
Rightmost derivation (RMD)	The rightmost non-terminal is replaced first at every step	⇒rm

 

Example: Grammar  S → AB,  A → a,  B → b,  string ab.

Derivation	Steps
LMD	S ⇒ AB ⇒ aB ⇒ ab
RMD	S ⇒ AB ⇒ Ab ⇒ ab

Both orders give the same string. In S → aSb | ab there is only one non-terminal at each step, so LMD and RMD coincide.

2.3  Parse Tree (Derivation Tree)

A parse tree is a tree that shows how a string is generated from the start symbol by applying production rules. It represents the syntactic structure of the string.

Component	Meaning
Root	The start symbol of the grammar
Internal nodes	Non-terminal symbols
Leaf nodes	Terminal symbols or ε
Branches	Application of a production rule (children = right-hand side, left to right)
Yield	The string obtained by reading the leaves from left to right

2.4  Example — Parse Tree for aabb

Grammar: S → aSb | ab      Derivation:  S ⇒ aSb ⇒ aabb

Fig. 1  Parse tree of aabb  (circles = non-terminals, boxes = terminals)

Reading the leaves from left to right gives the yield  a a b b = aabb.

2.5  Uses of Parse Trees

●      To represent the structure of a generated string

●      To understand how production rules are applied

●      To check the syntax of programming languages

●      To support syntax analysis in compiler design

●      To identify ambiguity in a grammarrammar

 

  TOPIC 3  Ambiguity in Context-Free Grammar 

3.1  Definition

A CFG is ambiguous if there exists at least one string in its language that has more than one distinct parse tree. Equivalently, that string has more than one leftmost derivation (or more than one rightmost derivation).

Ambiguous  ⇔  some w ∈ L(G) has two or more parse trees

3.2  Example of an Ambiguous Grammar

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

The string has two different leftmost derivations:

Parse Tree	Leftmost Derivation	Meaning
Tree 1	E ⇒ E+E ⇒ id+E ⇒ id+E*E ⇒ id+id*E ⇒ id+id*id	id + (id * id)  — multiplication first
Tree 2	E ⇒ E*E ⇒ E+E*E ⇒ id+E*E ⇒ id+id*E ⇒ id+id*id	(id + id) * id  — addition first

 

Fig. 2  Parse Tree 1:  id + (id * id)

Fig. 3  Parse Tree 2:  (id + id) * id

Since the same string has two distinct parse trees, the grammar is ambiguous.

3.3  Types of Grammar Based on Ambiguity

Type	Meaning
Ambiguous grammar	At least one string has two or more distinct parse trees
Unambiguous grammar	Every string generated has exactly one parse tree
Inherently ambiguous language	A context-free language for which every possible CFG is ambiguous

     Remember: Ambiguity is a property of the grammar, not of the language — except for inherently ambiguous languages. There is no algorithm that decides whether an arbitrary CFG is ambiguous.

3.4  Disadvantages of Ambiguity

1.  It may give multiple interpretations to the same string.

2.  It creates difficulties in compiler design and syntax analysis.

3.  It may cause uncertainty in operator precedence and associativity.

4.  It can make the meaning of a program unclear.

3.5  Methods to Remove Ambiguity

●      Rewrite the grammar using separate non-terminals for different precedence levels.

●      Define operator precedence explicitly (higher precedence = deeper in the grammar).

●      Specify associativity — left-recursive rules give left associativity.

●      Use production rules that force a unique parse tree.

3.6  Example — Unambiguous Grammar for Expressions

Non-terminal	Level	Productions
E	Addition (lowest precedence)	E → E + T | T
T	Multiplication	T → T * F | F
F	Operands (highest precedence)	F → id

Now id + id * id has only one parse tree, in which * binds tighter than + and both operators are left-associative:

Fig. 4  The only parse tree of id + id * id in the unambiguous grammar

 

  TOPIC 4  CFG Simplification 

4.1  Introduction

CFG simplification reduces the complexity of a grammar by removing unnecessary productions and symbols without changing the language it generates.

Simplified grammar G′ :  L(G′) = L(G)

4.2  Three Steps — In This Order

Step	Eliminate	Form Removed
1	ε-productions (null productions)	A → ε
2	Unit productions	A → B   (A, B ∈ V)
3	Useless symbols	Non-generating and unreachable symbols

Note: If ε belongs to the original language, preserve it using a new start symbol S₀ → S | ε.

4.3  Elimination of ε-Productions

A production A → ε is an ε-production (null production). A non-terminal is nullable if A ⇒^* ε.

Step	Action
1	Find all nullable non-terminals.
2	Find every production that has a nullable symbol on its right-hand side.
3	Add new productions by omitting the nullable symbols in every possible combination (never add A → ε).
4	Remove all ε-productions.
5	If ε ∈ L(G), keep it by adding a new start symbol S₀ → S | ε.

  Example

Given: S → AB      A → aA | ε      B → bB | ε

●      Nullable symbols: A and B (directly), and S (because S → AB with both nullable).

●      S → AB gives the new productions S → A and S → B (omitting B, omitting A).

●      A → aA gives A → a;   B → bB gives B → b.   Remove A → ε and B → ε.

●      ε ∈ L(G), so add S₀ → S | ε.

Result
S₀ → S | ε
S → AB | A | B
A → aA | a
B → bB | b

4.4  Elimination of Unit Productions

A production A → B, where both A and B are non-terminals, is a unit production.

Step	Action
1	Identify all unit productions.
2	Find the non-unit productions of the non-terminal on the right-hand side.
3	Add those productions to the left-hand-side non-terminal.
4	Remove the unit production.
5	Repeat until no unit production remains.

Example 1

Given: S → A      A → a | b

Replace S → A by the productions of A:   S → a | b      A → a | b.   (A is now unreachable and is removed in the next stage.)

  Example 2 — chain of unit productions

Given: S → A | Ba      A → B | a      B → b

Non-terminal	Unit-derivable symbols	New productions
S	A, B	S → Ba | a | b
A	B	A → a | b
B	—	B → b

After removing A (unreachable):   S → Ba | a | b      B → b.

4.5  Elimination of Useless Symbols

A symbol is useless if it cannot contribute to deriving a terminal string from the start symbol. Two kinds exist:

Kind	Meaning	Test
Non-generating	Cannot derive any terminal string	Not in the set of symbols that derive terminal strings
Unreachable	Cannot be reached from the start symbol	Not reachable from S through productions

 

y	Action
1	Find all generating non-terminals (those deriving strings of terminals, possibly ε).
2	Remove non-generating symbols and every production containing them.
3	From S, find all reachable non-terminals.
4	Remove unreachable symbols and their productions.

Example

Given: S → AB | a      A → aA      B → b

●      Generating symbols: B (B → b) and S (S → a). A is non-generating, because A → aA never ends.

●      Remove A and S → AB:   S → a      B → b.

●      From S only S is reachable, so B is unreachable — remove it.

Simplified grammar:  S → a

  TOPIC 5  Chomsky Normal Form (CNF) 

5.1  Definition

A CFG is in Chomsky Normal Form if every production has one of the following forms:

No.	Form	Meaning
1	A → BC	Exactly two non-terminals
2	A → a	Exactly one terminal
3	S → ε	Only if ε ∈ L(G), and S must not appear on any right-hand side

 

Here A, B, C are non-terminals, a is a terminal, and S is the start symbol.

5.2  Examples of CNF Productions

Production	Valid in CNF?	Reason
S → AB	Yes	Two non-terminals
A → a	Yes	One terminal
B → CD	Yes	Two non-terminals
S → ε	Yes (conditionally)	Empty string production for the start symbol
S → aB	No	Terminal and non-terminal together
A → BCD	No	Three non-terminals
A → B	No	Unit production

 

5.3  Steps to Convert a CFG into CNF

Step	Action
1	New start symbol: if S occurs on a right-hand side, add S₀ → S.
2	Remove null productions (A → ε), preserving ε if it is in the language.
3	Remove unit productions (A → B).
4	Remove useless symbols (non-generating and unreachable).
5	Replace terminals in longer productions: A → aB becomes A → XB and X → a.
6	Break long productions: A → B₁B₂⋯Bₖ (k > 2) becomes A → B₁C₁, C₁ → B₂C₂, …, Ck−2 → Bk−1Bk.
7	Verify that every production has a permitted CNF form.

5.4  Example 1

Given: S → aAB      A → a      B → b

  Step 1: Replace the terminal in the longer production

Introduce X → a and rewrite S → aAB as S → XAB.

  Step 2: Reduce the long production

S → XAB has three symbols. Introduce C → AB, so S → XC.

  Step 3: Final grammar

CNF Grammar
S → XC
C → AB
X → a
A → a
B → b

Verification: every production is of the form A → BC or A → a, so the grammar is in CNF.

5.5  Example 2 — Grammar for aⁿbⁿ

Given: S → aSb | ab

Stage	Productions
Replace terminals (X → a, Y → b)	S → XSY | XY      X → a      Y → b
Break S → XSY (C → SY)	S → XC | XY      C → SY      X → a      Y → b

Check for aabb:  S ⇒ XC ⇒ aC ⇒ aSY ⇒ aXYY ⇒ aaYY ⇒ aabY ⇒ aabb  (7 = 2·4 − 1 steps), so aⁿbⁿ (n ≥ 1) is preserved.

Property of CNF: Every derivation of a string of length n ≥ 1 takes exactly 2n − 1 steps, and every parse tree is a binary tree.

5.6  Applications of CNF

●      Used in the CYK (Cocke–Younger–Kasami) algorithm to decide whether a string belongs to a context-free language.

●      Simplifies the structure of context-free grammars.

●      Helps in the theoretical analysis of context-free languages and parsing.

  TOPIC 6  Greibach Normal Form (GNF) 

6.1  Definition

A CFG is in Greibach Normal Form if every production begins with a terminal symbol followed by zero or more non-terminals:

A → a A₁A₂⋯Aₙ        (n ≥ 0)

●      A, A₁, …, Aₙ are non-terminals;  a is a terminal.

●      n ≥ 0, so A → a is allowed.

●      S → ε may be permitted when ε ∈ L(G), provided S does not appear on any right-hand side.

6.2  Examples of GNF Productions

Production	Valid in GNF?	Reason
S → a	Yes	Begins with a terminal
A → aB	Yes	Terminal followed by a non-terminal
S → aAB	Yes	Terminal followed by non-terminals
B → bBC	Yes	Begins with a terminal
S → aB | bC	Yes	Both alternatives begin with terminals
S → AB	No	Begins with a non-terminal
A → Ba	No	Begins with a non-terminal

6.3  Example of a Grammar in GNF

Grammar: S → aAB | bB      A → aA | a      B → bB | b

Every production begins with a terminal (a or b), so the grammar is in Greibach Normal Form.

6.4  Steps to Convert a CFG into GNF

Step	Action
1	New start symbol: if S occurs on a right-hand side, introduce a new start symbol.
2	Remove null productions, preserving ε if it is in the language.
3	Remove unit productions.
4	Remove useless symbols.
5	Eliminate left recursion (direct and indirect).
6	Substitute: replace a leading non-terminal by its productions until every right-hand side begins with a terminal.
7	Verify that every production has the form A → aA₁A₂⋯Aₙ.

6.5  Removing Direct Left Recursion

A production A → Aα is left-recursive. If the productions of A are

A → Aα₁ | Aα₂ | ⋯ | β₁ | β₂ | ⋯

(each β_j does not begin with A), replace them by, using a new non-terminal Z:

A → β₁ | β₂ | ⋯ | β₁Z | β₂Z | ⋯

Z → α₁ | α₂ | ⋯ | α₁Z | α₂Z | ⋯

6.6  Worked Examples

  Example 1: S → aSb | ab

Introduce B → b and replace b on the right-hand sides:

GNF Grammar
S → aSB | aB
B → b

Every production begins with a terminal, so the grammar is in GNF and still generates aⁿbⁿ (n ≥ 1).

  Example 2: Removing left recursion — A → Aa | b

Here α = a and β = b. Apply the rule with a new non-terminal Z:

GNF Grammar
A → bZ | b
Z → aZ | a

Both grammars generate the language b a^* = {b, ba, baa, …}.

6.7  Difference Between CNF and GNF

Chomsky Normal Form (CNF)	Greibach Normal Form (GNF)
A → BC  or  A → a	A → aA₁A₂⋯Aₙ
Right side has two non-terminals or one terminal	Right side starts with a terminal
A → BC is valid	A → BC is invalid
Derivation of a string of length n takes 2n − 1 steps	Derivation of a string of length n takes exactly n steps
Useful in the CYK parsing algorithm	Useful in studying derivations and constructing pushdown automata

6.8  Applications of GNF

●      Theoretical study of context-free languages.

●      Constructing pushdown automata from context-free grammars.

●      Each production step generates exactly one terminal, so a non-empty string of length n is derived in exactly n steps.

 

  TOPIC 7  Pumping Lemma for Context-Free Languages 

7.1  Statement

The pumping lemma is a theorem used to prove that certain languages are NOT context-free. If L is a context-free language, then there is a positive integer p (the pumping length) such that every string z ∈ L with |z| ≥ p can be written as

z = uvwxy

satisfying the following three conditions:

No.	Condition	Notation	Meaning
1	Length condition	|vwx| ≤ p	The middle portion vwx is short
2	Non-empty pumping parts	|vx| ≥ 1	At least one of v, x is non-empty
3	Pumping condition	uviwxiy ∈ L  for all i ≥ 0	Pumping v and x together keeps the string in L

 

Part	Role
u and y	Fixed parts (start and end of the string)
v and x	Parts that are pumped together
w	Middle part that stays unchanged

 

Value of i	Resulting String	Effect
i = 0	uwy	Both v and x removed
i = 1	uvwxy = z	Original string
i = 2	uvvwxxy	Each of v and x repeated twice

 

7.2  Example — Prove that L = {aⁿbⁿcⁿ | n ≥ 1} is not context-free

  Step 1: Assume L is context-free

Then a pumping length p exists.

  Step 2: Choose a string

z = a^pb^pc^p

Clearly z ∈ L and |z| = 3p ≥ p.

  Step 3: Divide the string

Let z = uvwxy with |vwx| ≤ p and |vx| ≥ 1. The block of b’s alone has length p, so vwx cannot contain both an a and a c (that would need length at least p + 2). Hence vwx touches at most two kinds of symbols. All possible positions are:

Case	Where vwx lies	Effect of pumping with i = 0 (string uwy)
1	Only inside ap	Fewer a’s; b’s and c’s stay p  →  counts unequal
2	Only inside bp	Fewer b’s; a’s and c’s stay p  →  counts unequal
3	Only inside cp	Fewer c’s; a’s and b’s stay p  →  counts unequal
4	Across a’s and b’s	Fewer a’s and/or b’s; c’s stay p  →  counts unequal
5	Across b’s and c’s	Fewer b’s and/or c’s; a’s stay p  →  counts unequal

  Step 4: Conclusion

In every case uwy ∈ L, which contradicts the lemma (uv⁰wx⁰y ∈ L). Therefore:

L = {aⁿbⁿcⁿ | n ≥ 1} is not context-free

7.3  Steps to Apply the Pumping Lemma in Examinations

1.  Assume that the given language is context-free.

2.  Let p be its pumping length.

3.  Choose a suitable string z ∈ L with |z| ≥ p.

4.  Write z = uvwxy satisfying |vwx| ≤ p and |vx| ≥ 1.

5.  Consider ALL possible positions of v and x.

6.  Choose a pumping value, usually i = 0 or i = 2.

7.  Show that the resulting string does not belong to L.

8.  State the contradiction and conclude that L is not context-free.

7.4  Pumping Lemma for Regular Languages vs CFLs

Regular Languages	Context-Free Languages
String divided into three parts: xyz	String divided into five parts: uvwxy
xyiz ∈ L	uviwxiy ∈ L
|xy| ≤ p,  |y| > 0	|vwx| ≤ p,  |vx| ≥ 1
Pumps one substring	Pumps two substrings, v and x, together
Used to prove a language is not regular	Used to prove a language is not context-free

 

Important note: The pumping lemma is a necessary property of every context-free language, but it is not sufficient. Satisfying the lemma does not prove that a language is context-free.

Recap — Unit IV

#	Topic	Key Idea to Remember
1	CFG	G = (V, T, P, S);  productions A → α;  L(G) = {w ∈ T* | S ⇒* w}
2	Derivations & Parse Trees	LMD replaces leftmost non-terminal; RMD the rightmost; yield = leaves left to right
3	Ambiguity	Ambiguous ⇔ a string has two parse trees; fix with precedence levels (E, T, F)
4	Simplification	Order: remove ε-productions → unit productions → useless symbols
5	CNF	A → BC  or  A → a;  derivation of length-n string takes 2n − 1 steps; used in CYK
6	GNF	A → aA₁⋯Aₙ;  remove left recursion; derivation takes n steps; used for PDA
7	Pumping Lemma (CFL)	z = uvwxy,  |vwx| ≤ p,  |vx| ≥ 1,  uviwxiy ∈ L — proves NON-context-free