ZeePedia

Total language tree, Regular Grammar

<< Polish Notation (o-o-o)
Null Production >>
img
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ÆaSa|bSb|a|b|L
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
non-terminals. 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 Æ aa|bX|aXX
X Æ ab|b
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 Æ X|b, X Æ aX
then following will be the total language tree of the above CFG
101
img
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 Æ aSb|ab 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 Æ bS|aA
A Æ aB|bS
B Æ aB|bB|L
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
img
Theory of Automata
(CS402)
Examples
The CFG S Æ aaS|bbS|L 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 Æ aA|bB, A Æ aS|a, B Æ bS|b 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 Æ aaS|bbS| 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