Prove with example that the CFG given below isambiguous: X à aX | bX |aaX | ^ So

Question

Prove with example that the CFG given below isambiguous:

X à aX | bX |aaX | ^

Explanation / Answer

b)A CFG is called ambiguous if it for at least one wordin the language that it generates there are two possiblederivations of the word. Given; X->aX |bX|aaX/^      Now first take   X=>aX                                 =>aaaX       (here take firstleft X->aaX)                                               =>aaabX    (here take left X->bX)                                 =>aaab^     (here take X->^and ^ value is null so not taken)                                 =>aaab----------------------------------->1       Now take X=>aaX                         =>aaaX         (here take X->aX)                          =>aaabX     (here take X->bX )                          =>aaab^       (here takeX->^)                           =>aaab------------------------------------------>2 here clearly observed 1,2 derivations are equal.so givenstring is ambigious. i hope it is helpful to you...........

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.