CS402 Ass # 6 Sol

Question: Mark:5+5+5+5 Consider the following Context Free Grammar (CFG) S → aY | Ybb | Y X → Λ | a Y → aXY | bb | XXa a) Is the CFG ambiguous, if Yes then justify your answer. b) Draw a Total Language Tree (TLT) for the given CFG. c) Convert the CFG into CNF. d) Build the PDA corresponding to the CFG (in CNF) of part (c).

Solution:-

i think it will help u>>>>>>

Question: Mark:5+5+5+5 Consider the following Context Free Grammar (CFG)
S → aY | Ybb | Y

X → Λ | a
Y → aXY | bb | XXa a) Is the CFG ambiguous, if Yes then justify your answer. b) Draw a Total Language Tree (TLT) for the given CFG. c) Convert the CFG into CNF. d) Build the PDA corresponding to the CFG (in CNF) of part (c).


Part a

this CFG Is not ambiguous because any string in not shown two derivation tree.



Part b

second is its total language tree may be arbitrary wide as well as infinity long.



Part c

CFG Into CNF removing null and unit production

s-> Ay| yBB | b
x-> a | a
y-> Axy | Ax |BB | xxa| xx | xA | a
A->a
B->b

part d

This is wrong.I was not able to convert it into CNF, but I am very close to do it so!
S->aY|Ybb|Y
X->^|a
Y->aXY|bb|XXa
null production
Y->aY|bb|Xa|a
after removing null production
S->aY|Ybb|Y
X->a
Y->aY|bb|Xa|a
Unit production
S->Y
S->Y->aY gives S->abb (Y->bb)
S->Y->aY gives S->aa (Y->a)
S->Y->aY->aXa gives S->aaa (X->a)
New CFG will be
S->aY|Ybb|abb|aa|aaa
X->a
Y->aY|bb|Xa|a
(i am stuck here)
 

Please do make changes in these assignment otherwise every one who copy this assignment as it is will awarded zero marks 

NOTE: - These Assignments OR Quiz are just for idea, so kindly don't copy it, after viewing it make your own. Thanks We always try our best to upload 100% correct solution BUT it is requested that you kindly review it before submission, please BEST OF LUCK, Thanks to those students those send me Assignments and quizzes. If you have any Assignment and quiz kindly send at jamilbookcenter@yahoo.com