Normalization of Context-free Grammars
Prof. (Dr.) K.R. Chowdhary
Former Professor & Head, Department of Computer Sc. & Engineering
MBM Engineering College, Jodhpur

kr chowdhary

TOC

1/ 9

K.R. Chowdhary

Theory of Computation
Automata, Formal Languages, Computation and Complexity
Focuses on pedagogy in its writing, that represents a refreshing
approach
Ensures comprehensive and enjoyable learning
Undergone a rigorous classroom testing

©2025

Get 20% off with this code: SPRAUT
Available on Springer Nature Link
Please note that promotional coupons are only valid for English-language Springer, Apress, and Palgrave Macmillan books
& eBooks and are redeemable on link.springer.com only. Titles affected by fixed book price laws, forthcoming titles and
titles temporarily not available on Springer Nature Link are excluded from promotions, as are reference works, handbooks,
encyclopedias, subscriptions, or bulk purchases. The currency in which your order will be invoiced depends on the billing
address associated with the payment method used, not necessarily your home currency. Regional VAT/tax may apply.
Promotional prices may change due to exchange rates. Promotions are valid for individual customers only. Booksellers,
book distributors, and institutions such as libraries and corporations please visit springernature.com/contact-us.
Promotions do not work in combination with other discounts or gift cards.

link.springer.com/book/
9789819762347

Introduction to Simplification of Grammars
Parsing becomes easier if we add full generality in the grammar G .
In simplification of G , we remove 1) null-productions (also called
ε−productions), 2) unit-productions (chain-rules), and 3)
non-reachable symbols and corresponding productions.
But, the generating power of the grammar remains the same.
A variable symbol is useful if it appears in some derivation,
otherwise it is useless.
if ε ∈
/ L(G ), then all the ε−productions can be removed from the
grammar.
Normal Forms: Is some restrictions in the productions rules, for the
right hand side of a production, so that all the productions are in
some standard form. Two types normal forms exits:
CNF: Chomsky Normal Form Grammar: All the productions are
like: A → BC , A → a, where A, B, C ∈ V and a ∈ Σ.
GNF: Greibach Normal Form Grammar: All the productions are
like A → aα, where a ∈ Σ and α ∈ V ∗ .
kr chowdhary

TOC

2/ 9

ε-productions, useless productions
Productions of the form A → ε are called null productions. All these
productions can be eliminated from grammar if ε ∈
/ L(G ). Hence, in
this case the generating power of G remains unchanged.
If A ⇒∗ ε then variable A is called nullable.
If B → X1 X2 . . . Xn , then Xi can be dropped in this production if
∃Xi → ε. Such Xi ’s are called nullable. But if B → ε, then Xi ’s
cannot be eliminated.
Useless symbols and productions: Given the derivation
S ⇒∗ αX β ⇒∗ w ∈ Σ∗ , where α, β ∈ (V ∪ Σ)∗ , here X is useful
because it appears in some derivation.
Example
S → aSb|ε, B → bB, has B useless symbol and B → bB as useless
production. This is because B is not reachable from S, neither B
terminates to null or terminal.
Example
S → A, A → aA|ε, B → bA, has B as useless symbol and B → bA as
useless production.
kr chowdhary

TOC

3/ 9

Theorem
Theorem
If G = (V , Σ, S, P) with L(G ) ̸= φ , then there is an equivalent grammar
G ′ = {V ′ , Σ, S, P ′ }, such that G ′ does not contain useless symbols and
productions, and L(G ) = L(G ′ ).
Proof.
We follow the following algorithm to systematically construct G ′ :
1. For Ai → u,, where u ∈ Σ∗ , move Ai to V ′ , and Ai → u to P ′ .
2. V = V − {Ai }, P = P − {Ai → u}.
3. while ∃Aj → X1 X2 . . . Xn ∈ P, where Xi ∈ V ′ , or Xi ∈ Σ do
a. V ′ = V ′ ∪ {Aj },
b. P ′ = P ′ ∪ {Aj → X1 X2 . . . Xn },
c. V = V − {Aj }, P = P − {Aj → X1 X2 . . . Xn }
enddo
The tree for above is shown in next slide. The grammar constructed as
G ′ does not contains null productions as the same were removed in
advance, it does not contain the useless symbols and productions.
kr chowdhary

TOC

4/ 9

Theorem condinued . . .

The figure shows that first of all we construct the bottom most subtree,
Ai , then Aj , and then A, till finally to S. This way only reachable
symbols from S, and corresponding productions are move to grammar G ′ .
Therefore, no null or useless productions or symbols have been moved
into the grammar G ′ . Thus generating power of G and G ′ are same.

kr chowdhary

TOC

5/ 9

Removing unit productions

Productions of the form A → B, where A, B ∈ V are called unit
productions.
Having removed useless symbols and productions, and
ε−productions, we remove the unit-productions.
Example: Given productions A → B, B → bB|c, it can be
substituted by single production:
A → bB|c. 2

If there is sequence of unit productions, and it gives a look of chain
like: A ⇒∗ B, then all the unit productions can be removed
systematically. But, if there is situation like: A ⇒∗ B, due to
A ⇒ BC ⇒ B, and C → ε, then A ⇒∗ B is not a chain.

kr chowdhary

TOC

6/ 9

CNF Theorem
Theorem
If there is grammar G = (V , Σ, S, P, there exists an equivalent grammar
G ′ = (V ′ , Σ′ , S, P ′ ) without unit-productions, ε−productions, and useless
symbols and productions, and is CNF .
Proof.
The ε−productions, unit-productions, and useless-productions and
symbols can be removed using the mathods discussed earlier. This
does not effect the generating power of the grammar.
The grammar availabe now has following format: A → X1 X2 . . . Xn .
For n = 1, the right hand side of a production has single symbol.
This will be termal only, as all the unit productions have been
removed.
For X ≥ 2, there is Xi ∈ (V ∪ Σ). If Xi is terminal, say a, then
substitute a by Ci and introduce a new production Ci → a.

kr chowdhary

TOC

7/ 9

CNF Theorem . . .

All the productions are now of the form: A → a or A → C1 C2 . . . Cn .
All the productions like A → C1 C2 . . . Cn are reduced to A → BC as
follows: (A → C1 C2 is already CNF). For n > 2, modify the
productions as follows:
A → C1 D1
D1 → C2 D2
...
Dn−3 → Cn−2 Dn−2
Dn−2 → Cn−1 Dn .

This proves the theorem. 2

kr chowdhary

TOC

8/ 9

Bibliography

Chowdhary, K.R. (2025). Regular Languages. In: Theory of
Computation. Springer, Singapore.
https://doi.org/10.1007/978-981-97-6234-7_7

kr chowdhary

TOC

9/ 9