

Theory of
Automata
(CS402)
Theory of
Automata
Lecture
N0. 34
Reading
Material
Introduction
to Computer Theory
Chapter
12,13
Summary
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 Æ aS  bS 
aaS  L
It can be
observed that the word aaa
can be derived from more
than one production trees.
Thus, the above
CFG
is
ambiguous. This ambiguity
can be removed by removing
the production S Æ aaS
Example
Consider
the CFG of the language
PALINDROME
SÆaSabSbabL
It may be
noted that this CFG is
unambiguous as all the words of
the language PALINDROME can
only be
generated
by a unique production tree.
It may be
noted that if the production
S Æ
aaSaa is
added to the given CFG, the
CFG thus obtained will be
no
more
unambiguous.
Total
language tree
For a
given CFG, a tree with
the start symbol S as its
root and whose nodes
are working strings of terminals
and
nonterminals.
The descendants of each node
are all possible results of
applying every production to
the working
string.
This tree is called total
language tree.
Example
Consider
the following CFG
S Æ aabXaXX
X Æ abb
then
the total language tree for
the given CFG may
be
S
aa
aXX
bX
aXb
abb
abX
bab
bb
aabb
aabX
aXab
abb
abab
aabb
aabab
abab
aabab
It may be
observed from the above total
language tree that dropping
the repeated words, the
language generated
by the
given CFG is {aa, bab,
bb, aabab, aabb, abab,
abb}
Example
Consider
the following CFG
S Æ Xb, X
Æ
aX
then
following will be the total
language tree of the above
CFG
101
Theory of
Automata
(CS402)
S
X
b
aX
Note: It is to
be
noted
that the
only
word in
aaX
this
language
is
b.
∂
aaa
...aX
Regular
Grammar
All
regular languages can be
generated by CFGs. Some
nonregular languages can be
generated by CFGs but not
all
possible languages can be
generated by CFG, e.g.
the
CFG S Æ aSbab
generates the
language
{anbn:n=1,2,3, ...},
which is nonregular.
Note: It is to be
noted that for every
FA, there exists a CFG
that generates the language
accepted by this FA.
Example
Consider
the language L expressed by (a+b)*aa(a+b)*
i.e.the
language of strings, defined
over Â ={a,b},
containing
aa. To
construct the CFG corresponding to L,
consider the FA accepting L, as
follows
a,b
a
b
a
B+
S
A
b
CFG
corresponding to the above FA may
be
S Æ bSaA
A Æ aBbS
B Æ aBbBL
It may be
noted that the number of terminals in
above CFG is equal to the
number of states of corresponding FA
where the
nonterminal S corresponds to the
initial state and each
transition defines a production.
Semiword
A
semiword is a string of terminals (may be none)
concatenated with exactly
one nonterminal on the right
i.e.
a
semiword, in
general, is of the following
form
(terminal)(terminal)...
(terminal)(nonterminal)
word
A word is
a string of terminals. L is also a
word.
Theorem
If every
production in a CFG is one of
the following forms
Nonterminal
Æ
semiword
Nonterminal
Æ
word
then
the language generated by
that CFG is regular.
Regular
grammar
Definition
A CFG is
said to be a regular
grammar if it
generates the regular
language i.e.
a
CFG is said to be a regular
grammar
in
which each production is one
of the two forms
Nonterminal
Æ
semiword
Nonterminal
Æ
word
102
Theory of
Automata
(CS402)
Examples
The
CFG S Æ aaSbbSL is a
regular grammar. It may be observed that
the above CFG generates
the language
of
strings expressed by the RE
(aa+bb)*.
The
CFG S Æ aAbB, A Æ aSa, B
Æ
bSb is a
regular grammar. It may be observed that
the above CFG
generates
the language of strings
expressed by RE (aa+bb)+.
Following
is a method of building TG corresponding to
the regular grammar.
TG for
Regular Grammar
For
every regular grammar there
exists a TG corresponding to the regular
grammar.
Following
is the method to build a TG
from the given regular
grammar
Define
the states, of the required
TG, equal in number to that of
nonterminals of the given regular
grammar. An
additional
state is also defined to be
the final state. The
initial state should correspond to
the nonterminal S.
For
every production of the
given regular grammar, there
are two possibilities for
the transitions of the
required
TG
If the
production is of the form
nonterminal Æ semiword,
then transition of the required TG
would start from
the
state
corresponding to the nonterminal on the
left side of the production
and would end in the
state
corresponding to
the nonterminal on the right
side of the production, labeled by string of terminals
in semiword.
If the
production is of the form
nonterminal Æ word,
then transition of the TG would
start from the
state
corresponding to
nonterminal on the left side
of the production and would
end on the final state of
the TG,
labeled by
the word.
Example
Consider
the following CFG
S Æ aaSbbS
L
The TG
accepting the language
generated by the above CFG
is given below
aa
L
bb
+
S
The
corresponding RE may be (aa+bb)*.
103
Table of Contents:

