Recap Lecture: Example of Trees, Polish Notation, Examples, Ambiguous CFG, Example

Recap lecture
Example of trees, Polish Notation,

examples, Ambiguous CFG, example,
Example
Consider the following CFG
S  aS | bS | aaS | Λ
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
Following is another example
Example
Consider the CFG of the language
PALINDROME
S  aSa|bSb|a|b|Λ
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. Following is an example of
total language tree
Example
S  aa|bX|aXX
X  ab|b, then the total language tree for the
given CFG may be
S
aa aXX
bX
aXb
abX abb
bab bb
aabb
aabX aXab
abab abb
aabab aabb aabab abab

Example continued …
It may be observed from the previous total
language tree that dropping the repeated
words, the language generated by the given
CFG is
{aa, bab, bb, aabab, aabb, abab, abb}
Example
S  X|b, X  aX
then following will be the total language tree of
the above CFG S
X b
Note: It is to be aX
noted that the
only word in aaX
…
this language aaa …aX

is b.
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. Following is an example
in this regard
Regular grammar continued …
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
Regular grammar continued …
a,b
b a
A a
S- B+
b
CFG corresponding to the above FA may be
S  bS|aA
A  aB|bS
B  aB|bB|Λ
It may be noted that the number of non-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.
Regular Grammar continued …
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. Λ is also
a word.
Theorem
If every production in a CFG is one of
the following forms
1. Nonterminal  semiword
2. 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
Examples
1. The CFG S  aaS|bbS| Λ
is a regular grammar. It may be observed that the
above CFG generates the language of strings
expressed by the RE (aa+bb)*.
2. 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
1. 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.
2. For every production of the given regular
grammar, there are two possibilities for the
transitions of the required TG
Method continued …
(i) 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.
Method continued …
(ii) 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. Following is
an example in this regard
Example
S  aaS|bbS|Λ
The TG accepting the language generated by
the above CFG is given below
aa
bb S- Λ +
The corresponding RE may be (aa+bb)*.

SummingUP
• 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

Recap Lecture: Example of Trees, Polish Notation, Examples, Ambiguous CFG, Example

Uploaded by

Copyright:

Available Formats

Recap Lecture: Example of Trees, Polish Notation, Examples, Ambiguous CFG, Example

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Recap Lecture: Example of Trees, Polish Notation, Examples, Ambiguous CFG, Example

Uploaded by

Copyright:

Available Formats

Recap lecture

Example of trees, Polish Notation,

aabab aabb aabab abab

this language aaa …aX

(i) If the production is of the form

The corresponding RE may be (aa+bb)*.

You might also like