

Theory of
Automata
(CS402)
Theory of
Automata
Lecture
N0. 36
Reading
Material
Introduction
to Computer Theory
Chapter
13,14
Summary
Chomsky
Normal Form, Theorem regarding
CNF, examples of converting
CFG to be in CNF, Example of
an
FA corresponding to
Regular CFG, Left most and
Right most derivations, New
format of FAs.
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).
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
Theorem
All
NONNULL words of the CFL
can be generated by the corresponding
CFG which is in CNF i.e.
the
grammar in
CNF will generate the
same language except the
null string.
Following
is an example showing that a
CFG in CNF generates all
nonnull words of corresponding
CFL.
Example
Consider
the following CFG
S Æ aSabSbabaabb
To
convert the above CFG to be
in CNF, introduce the new productions
as
A Æ a, B Æ b, then
the new CFG will
be
S Æ ASABSBAABBab
AÆa
BÆb
Introduce
nonterminals R1 and R2 so that
S Æ AR1BR2AABBab
R1 Æ SA
R2 Æ SB
AÆa
BÆb
which is
in CNF.
It may be
observed that the above CFG
which is in CNF generates
the NONNULLPALINDROME, which
does
not
contain the null string.
Example
Consider
the following CFG
S Æ ABAB
A Æ aL
B Æ bL
Here S Æ ABAB is
nullable production and A Æ L, B Æ L are
null productions. Removing the
null productions
A Æ L and B
Æ
L,
and introducing the new
productions as
S Æ BABAABABBABAAAABBABBAB
Now S
Æ
AB
are unit productions to be eliminated as shown
below
S Æ A gives S
Æ
a (using
A Æ
a)
S Æ B gives S
Æ
b (using
B Æ
b)
Thus the
new resultant CFG takes
the form
107
Theory of
Automata
(CS402)
S Æ BABAABABBABAAAABBABBab,
A Æ
a, B
Æ
b.
Introduce
the nonterminal C where C Æ AB, so
that
S Æ BABAABABBABAAAABBABBab
S Æ BCACCBCAAACBABBab
AÆa
BÆb
C Æ AB
is the
CFG in CNF.
Example
To
construct an FA that accepts
the grammar
SÆabA
AÆbaB
BÆaAbb
The
language can be identified by
the three words generated as
follows
fi abA
S
fi abbaB
(using AÆbaB)
(using BÆbb)
fi abba
bb
fi abA
S
fi abbaB
(using AÆbaB)
fi abbaaA
(using BÆ aA)
fi abbaabaB
(using AÆ baB)
fi abbaababb
(using BÆ bb)
fi abA
S
fi abbaB
(using AÆbaB)
fi abbaaA
(using BÆ aA)
fi abbaabaB
(using AÆ baB)
fi abbaabaaA
(using BÆ aA)
fi abbaabaabaB
(using AÆ baB)
fi abbaabaababb
(using BÆ bb)
which
shows that corresponding language
has RE abba(aba)*bb.
Thus the FA accepting the
given CFG may be
a
S
A
B
+
a
b
b
a
b
b
a
a
b
b
a
a,b
Left
most derivation
a,b
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 Æ XXa
YÆYYb
then
following are the two
left most derivations of
aaabb
108
Theory of
Automata
(CS402)
fi XY
S fi XY
S
fi XXY
fi XXY
fi aXY
fi XXXY
fi aXXY
fi aXXY
fi aaXY
fi aaXY
fi aaaY
fi aaaY
fi aaaYY
fi aaaYY
fi aaabY
fi aaabY
=
aaabb
=
aaabb
Theorem
Any
word that can be generated
by a certain CFG has also a
left most derivation.
It is to be
noted that the above
theorem can be stated for
right most derivation as
well.
Example
Consider
the following CFG
SÆYX
X Æ XXb
YÆYYa
Following
are the left most
and right most derivations
of abbbb
S fi YX
fi YX
S
fi aX
fi YXX
fi aXX
fi YXb
fi abX
fi YXXb
fi abXX
fi YXbb
fi abbX
fi YXXbb
fi abbXX
fi YXbbb
fi abbbX
fi Ybbbb
=
abbbb
=
abbbb
A new
format for FAs
A class
of machines (FAs) has been
discussed accepting the
regular language i.e.
corresponding to a
regular
language
there is a machine in this
class, accepting that
language and corresponding to a machine
of this class
there is
a regular language accepted by
this machine. It has also
been discussed that there is
a CFG
corresponding to
regular language and CFGs
also define some nonregular
languages, as well
There is
a question whether there is a class of
machines accepting the CFLs?
The answer is yes. The
new
machines
which are to be defined are
more powerful and can be
constructed with the help of
FAs with new
format.
To define
the new format of an FA,
some terms are defined in
the next lecture.
109
Table of Contents:

