Chomsky Normal Form
Null Production
• Definition
• The production of the form nonterminal → Λ is said to be null production.
• Example: Consider the CFG, S → aA|bB|Λ, A → aa|Λ, B → aS
• Here S → Λ and A → Λ are null productions.
Note
• If a CFG has a null production, then it is possible to construct another CFG
without null production accepting the same language with the exception of
the word Λ i.e. if the language contains the word Λ then the new language
cannot have the word Λ. Following is a method to construct a CFG without
null production for a given CFG
• Method
Delete all the Null productions and add new productions e.g.
consider the productions of a certain CFG X → aNbNa, N → Λ, delete
the production N → Λ and using the
production X → aNbNa, add the new productions X → aNba, X → abNa
and X → aba
Thus the new CFG will contain the productions X →
aNba|abNa|aba|aNbNa
Note: It is to be noted that X → aNbNa will still be included in the new
CFG.
Nullable Production
• Definition
A production is called nullable production if it is of the form N → Λ
or
there is a derivation that starts at N and leads to Λ i.e. N1 → N2, N2 → N3, N3 → N4, …, Nn →Λ,
where N, N1,
N2, …, Nn are non terminals.
Example
Consider the following CFG
S → AA|bB, A → aa|B, B → aS | Λ
Here S → AA and A → B are nullable productions, while B → Λ is null a production.
Following is an example describing the method to convert the given CFG containing null productions
and
nullable productions into the one without null productions
• Example
• Consider the following CFG
• S → AA|bB, A → aa|B, B → aS | Λ
• Here S → AA and A → B are nullable productions, while B → Λ is null a
production.
• Following is an example describing the method to convert the given
CFG containing null productions and
• nullable productions into the one without null productions
Example
Consider the following CFG
S → XaY|YY|aX|ZYX
X → Za|bZ|ZZ|Yb
Y → Ya|XY|Λ
Z → aX|YYY
It is to be noted that in the given CFG, the productions S → YY, X → ZZ, Z → YYY are Nullable productions,
while Y → Λ is Null production.
Here the method of removing null productions, as discussed earlier, will be used along with replacing
nonterminals corresponding to nullable productions like nonterminals for null productions are replaced.
Thus the required CFG will be
S →XaY|Xa|aY|a|YY|Y|aX|ZYX|YX|ZX|ZY| X|Z
X → Za|a|bZ|b|ZZ|Z|Yb
Y → Ya|a|XY|X|Y
Z → aX|a|YYY|YY|Y
• Note
• While adding new productions all Nullable productions should be handled with care. All Nullable productions
• will be used to add new productions, but only the Null production will be deleted.
Unit production
• Unit production
• The productions of the form nonterminal → one nonterminal, is
called the unit production. Consider the following CFG
• S → A|bb A → B|b B → S|a
• Separate the unit productions from the nonunit productions as
shown below
Chomsky Normal Form
• If a CFG has only productions of the form
• nonterminal → string of two nonterminals
• Or nonterminal → one terminal
• then the CFG is said to be in Chomsky Normal Form (CNF).
Note
• It is to be noted that any CFG can be converted to be in CNF, if the null
productions and unit productions are
• removed. Also if a CFG contains nullable productions as well, then the
corresponding new production are also
• to be added. Which leads the following theorem
Chomsky Normal Form
Left most derivation
• Definition
• The derivation of a word w, generated by a CFG, such that at each
step, a production is applied to the left most
• nonterminal in the working string, is said to be left most derivation.
• It is to be noted that the nonterminal that occurs first from the left in
the working string, is said to be left most nonterminal.
Example
Consider the following CFG
S→XY
X → XX|a
Y→YY|b
then following are the two left most derivations of aaabb
