# Theory of Automata

<<< Previous Trees Next >>> Theory of Automata
(CS402)
Theory of Automata
Lecture N0. 32
Introduction to Computer Theory
Chapter 12
Summary
Examples of CFL, EVEN-EVEN, EQUAL, Language of strings containing bbb,
PALINDROME, {anbn}, Language of strings beginning and ending in different letters,
Parsing tree, example
Example
Â = {a,b}
productions:
S Æ SS
S Æ XS
SÆL
S Æ YSY
X Æ aa
X Æ bb
Y Æ ab
Y Æ ba
This grammar generates EVEN-EVEN language.
Example
Â = {a,b}
productions:
S Æ aB
S Æ bA
AÆa
A Æ aS
A Æ bAA
BÆb
B Æ bS
B Æ aBB
This grammar generates the language EQUAL(The language of strings, with number of a's equal to number of
b's).
Note
It is to be noted that if the same non-terminal have more than one productions, it can be written in single line
e.g. S Æ aS, S Æ bS, S Æ L can be written as S Æ aS|bS|L
It may also be noted that the productions S Æ SS|L always defines the language which is closed w.r.t.
concatenation i.e.the language expressed by RE of type r*. It may also be noted that the production S Æ SS
defines the language expressed by r+.
Example
Â = {a,b}
productions:
S Æ YXY
Y Æ aY|bY|L
X Æ bbb
It can be observed that, using prod.2, Y generates L. Y generates a. Y generates b. Y also generates all the
combinations of a and b. thus Y generates the strings generated by (a+b). It may also be observed that the above
95 Theory of Automata
(CS402)
CFG generates the language expressed by (a+b)*bbb(a+b)*. Following are four words generated by the given
CFG
fi YXY
S fi YXY
S
fi bYbbbaY
fi aYbbbL
fi bLbbbabY
fi abYbbb
fi bbbbabbY
fi abLbbb
fi bbbbabbaY
= abbbb
fi bbbbabbaL
= bbbbabba
S fi
fi YXY
YXY
S
fi
LbbbaY
fi bYbbbaY
fi
fi bLbbbaL
bbbabY
fi
= bbbba
bbbabaY
fi
bbbabaL
=
bbbaba
Example
Consider the following CFG
S Æ SS|XaXaX|L
X Æ bX|L
It can be observed that, using prod.2, X generates L. X generates any number of b's. Thus X generates the
strings generated by b*. It may also be observed that the above CFG generates the language expressed by
(b*ab*ab*)*.
Example
Consider the following CFG
Â = {a,b}
productions:
S Æ aSa|bSb|a|b|L
The above CFG generates the language PALINDROME. It may be noted that the CFG
S Æ aSa|bSb|a|b generates the language NON-NULLPALINDROME.
Example
Consider the following CFG
Â = {a,b}
productions:
S Æ aSb|ab|L
It can be observed that the CFG generates the language {anbn: n = 0,1,2,3, ...}. It may also be noted that the
language {anbn: n=1,2,3, ...} can be generated by the CFG, S Æ aSb|ab
Example
Consider the following CFG
S Æ aXb|bXa
X Æ aX|bX|L
The above CFG generates the language of strings, defined over Â={a,b}, beginning and ending in different
letters.
Trees
As in English language any sentence can be expressed by parse tree, so any word generated by the given CFG
can also be expressed by the parse tree, e.g. consider the following CFG
S Æ AA
A Æ AAA|bA|Ab|a
Obviously, baab can be generated by the above CFG. To express the word baab as a parse tree, start with S.
Replace S by the string AA, of nonterminals, drawing the downward lines from S to each character of this string
as follows
S
A
A
96 Theory of Automata
(CS402)
Now let the left A be replaced by bA and the right one by Ab then the tree will be
S
A
A
AA
b
b
Replacing both A's by a, the above tree will be
S
A
A
AA
b
b
aa
Thus the word baab is generated. The above tree to generate the word baab is called Syntax tree or Generation
tree or Derivation tree as well.
97