Recap Lecture 34

• Example of Ambiguous Grammar, Example

of Unambiguous Grammer
(PALINDROME), Total Language tree
with examples (Finite and infinite trees),
Regular Grammar, FA to CFG, Semi word
and Word, Theorem, Defining Regular
Grammar, Method to build TG for Regular
Grammar
 Example
Consider the following CFG
S  aA|bB
A  aS|a
B  bS|b, then the corresponding TG will be

A
a a
a
S- +
b
The corresponding RE may be (aa+bb) +. Following
b is another
example b
B
 Example
Consider the following CFG
S  aaS|bbS|abX|baX|
X  aaX|bbX|abS|baS,
then the corresponding TG will be

aa,bb aa,bb
ab,ba
 X
+ S-
ab,ba
The corresponding language is EVEN-EVEN.
 Null Production
Definition: The production of the form
nonterminal  
is said to be null production.
Example: Consider the following CFG
S  aA|bB|, A  aa|, B  aS
Here S   and A   are null productions.
Following is a note regarding the 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
 Null Production continued …
Method: Delete all the Null productions and add new
productions e.g.
consider the following productions of a certain CFG X 
aNbNa, N  , delete the production N   and using the
production
X  aNbNa, add the following new productions
X  aNba, X  abNa and X  aba
Thus the new CFG will contain the following
productionsX  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.
Following is an example
 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.
 Example continued …
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  Za|a|bZ|b|ZZ|Z|Yb
Y  Ya|a|XY|X|Y
Z  aX|a|YYY|YY|Y,
Following is another example
 Example
Consider the following CFG
S  XY, X  Zb, Y  bW
Z  AB, W  Z, A  aA|bA|
B Ba|Bb|.
Here A   and B   are null productions, while
Z  AB, W  Z are nullable productions. The
new CFG after, applying the method, will be
 Example continued …
S  XY
X  Zb|b
Y  bW|b
Z  AB|A|B
WZ
A  aA|a|bA|b
B Ba|a|Bb|b
 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.
Following is an example showing how to
eliminate the unit productions from a
given CFG.
 Unit production continued …
Example: Consider the following CFG
S  A|bb,
A  B|b,
B  S|a
Separate the unit productions from the nonunit
productions as shown below
unit prods. nonunit prods.
SA S  bb
AB Ab
BS Ba
 Example continued …
S  A gives S  b (using A  b)
S  A  B gives S  a (using B  a)
A  B gives A  a (using B  a)
A  B  S gives A  bb (using S  bb)
B  S gives B  bb (using S  bb)
B  S  A gives B  b (using A  b)
Thus the new CFG will be
S  a|b|bb, A  a|b|bb, B  a|b|bb.
Which generates the finite language {a,b,bb}.
 Chomsky Normal Form
Chomsky Normal Form (CNF): 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).
 Summing Up
• Examples of building TG’s corresponding
to the Regular Grammar, Null productions
with examples, Nullable productions with
examples, Unit production with example,
Chomsky Normal Form (Definition)