CS402 5th Assignment Due Date: 28 January, 2013
Assignment comprises of lectures No. 31-35.
Q 1: Marks [5+8]
Sà XYZ
Xà aX | bX | ^
Yà aY | bY | ^
Zà aZ | ^
a. Remove all NULL productions from the given grammar.
b. Remove all UNIT productions from the grammar obtained in part (a).
Q 2:
Sà mno | mA | nB | oC
Aà mX | ^
Bà nY | ^
Cà oZ | ^
Xà mn | m
Yà no | n
Zà om | o
Draw the total language tree for above CFG. Marks [7]
:::::::::::::::::::::::::::::Just idea:::::::::::::::::::::::::::::
to clear the points plzzz read carefully handouts page number 96,99.100
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
Null Production
Definition
The production of the form nonterminal → Λ is said to be null production.
Example: Consider the CFG, S → aA|bB|Λ, A → aa|Λ, B → aS
Here S → Λ and A → Λ are null productions.
Note
If a CFG has a null production, then it is possible to construct another CFG without null production accepting
the same language with the exception of the word Λ i.e. if the language contains the word Λ then the new
language cannot have the word Λ.
Following is a method to construct a CFG without null production for a given CFG
Method
Delete all the Null productions and add new productions e.g.
consider the productions of a certain CFG X → aNbNa, N → Λ, delete the production N → Λ and using the
production X → aNbNa, add the new productions X → aNba, X → abNa and X → aba
Thus the new CFG will contain the productions X → aNba|abNa|aba|aNbNa
Note: It is to be noted that X → aNbNa will still be included in the new CFG.
example unit production
Unit production
The productions of the form nonterminal → one nonterminal, is called the unit production.
Following is an example showing how to eliminate the unit productions from a given CFG.
Example
Consider the following CFG
S → A|bb
A → B|b
B → S|a
Separate the unit productions from the nonunit productins
unit prods. nonunit prods.
S → A S → bb
A → B A → b
B → S B → a
S → A gives S → b (using A → b)
S → A → B gives S → a (using B → a)
A → B gives A → a (using B → a)
A → B → S gives A → bb (using S → bb)
B → S gives B → bb (using S → bb)
B → S → A gives B → b (using A → b)
Thus the new CFG will be
S → a|b|bb, A → a|b|bb, B → a|b|bb.
Which generates the finite language {a,b,bb}.
Productions of the form A!B, where A,B 2 V are called unit productions.
Having removed useless symbols and productions, and e−productions, we remove the unit-productions.
Example: Given productions A!B,B !bB|c, it can be
substituted by single production:
A!bB|c. 2
If there is sequence of unit productions, and it gives a look of chain
like: A) B, then all the unit productions can be removed
systematically. But, if there is situation like: A) B, due to
A)BC )B, and C !e, then A) B is not a chain
Removing unit productions involves removing the productions that are unit productions, then adding new productions that exclude the productions that are unit productions. For example, if a grammar contained the rules:
A->C
B->cAd
C->a
Then you would remove A->C and add A->a.
Assignment comprises of lectures No. 31-35.
Q 1: Marks [5+8]
Sà XYZ
Xà aX | bX | ^
Yà aY | bY | ^
Zà aZ | ^
a. Remove all NULL productions from the given grammar.
b. Remove all UNIT productions from the grammar obtained in part (a).
Q 2:
Sà mno | mA | nB | oC
Aà mX | ^
Bà nY | ^
Cà oZ | ^
Xà mn | m
Yà no | n
Zà om | o
Draw the total language tree for above CFG. Marks [7]
:::::::::::::::::::::::::::::Just idea:::::::::::::::::::::::::::::
to clear the points plzzz read carefully handouts page number 96,99.100
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
Null Production
Definition
The production of the form nonterminal → Λ is said to be null production.
Example: Consider the CFG, S → aA|bB|Λ, A → aa|Λ, B → aS
Here S → Λ and A → Λ are null productions.
Note
If a CFG has a null production, then it is possible to construct another CFG without null production accepting
the same language with the exception of the word Λ i.e. if the language contains the word Λ then the new
language cannot have the word Λ.
Following is a method to construct a CFG without null production for a given CFG
Method
Delete all the Null productions and add new productions e.g.
consider the productions of a certain CFG X → aNbNa, N → Λ, delete the production N → Λ and using the
production X → aNbNa, add the new productions X → aNba, X → abNa and X → aba
Thus the new CFG will contain the productions X → aNba|abNa|aba|aNbNa
Note: It is to be noted that X → aNbNa will still be included in the new CFG.
example unit production
Unit production
The productions of the form nonterminal → one nonterminal, is called the unit production.
Following is an example showing how to eliminate the unit productions from a given CFG.
Example
Consider the following CFG
S → A|bb
A → B|b
B → S|a
Separate the unit productions from the nonunit productins
unit prods. nonunit prods.
S → A S → bb
A → B A → b
B → S B → a
S → A gives S → b (using A → b)
S → A → B gives S → a (using B → a)
A → B gives A → a (using B → a)
A → B → S gives A → bb (using S → bb)
B → S gives B → bb (using S → bb)
B → S → A gives B → b (using A → b)
Thus the new CFG will be
S → a|b|bb, A → a|b|bb, B → a|b|bb.
Which generates the finite language {a,b,bb}.
Productions of the form A!B, where A,B 2 V are called unit productions.
Having removed useless symbols and productions, and e−productions, we remove the unit-productions.
Example: Given productions A!B,B !bB|c, it can be
substituted by single production:
A!bB|c. 2
If there is sequence of unit productions, and it gives a look of chain
like: A) B, then all the unit productions can be removed
systematically. But, if there is situation like: A) B, due to
A)BC )B, and C !e, then A) B is not a chain
Removing unit productions involves removing the productions that are unit productions, then adding new productions that exclude the productions that are unit productions. For example, if a grammar contained the rules:
A->C
B->cAd
C->a
Then you would remove A->C and add A->a.
0 comments
Post a Comment