VUsolutions Transferred to AchiKhasi.com

From December 2011, this blog www.VUsolutions.blogspot.com is transferred to http://achikhasi.com/vu/ . So, you may visit http://achikhasi.com/vu/ for latest study related help.

Back to home VUsolutions

VUsolutions Fans Club [join us for MORE solutions]

VUsolutions on Facebook

CS402 Ass # 6 Solution

Thursday, July 29, 2010 Posted In Edit This

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 


Back to home VUsolutions

Shaadi.com: Just create ur account & find ur partner or EARN money, its reall & EASY

VUsolutions Followers (Join NOW and Get Extra Benefits)

Install LATEST toolbar having lot of features - GET solutions on Desktop

toolbar powered by Conduit
Caliplus 300x250 NoFlam VitoLiv 468x60 GlucoLo