Ambiguity in CFGs - Solved Problems (Set 1)

Compiler Design: Ambiguity in CFGs - Solved Problems (Set 1)
Topics discussed:
1. UGC-NET December 2018 solved PYQ of Ambiguity in Context Free Grammars.
2. UGC-NET June 2018 solved PYQ of Ambiguity in Context Free Grammars.
Follow Neso Academy on Instagram: @nesoacademy (bit.ly/2XP63OE)
Contribute: www.nesoacadem...
Memberships: bit.ly/2U7YSPI
Books: www.nesoacadem...
Website ► www.nesoacadem...
Forum ► forum.nesoacad...
Facebook ► goo.gl/Nt0PmB
Twitter ► / nesoacademy
Music:
Axol x Alex Skrindo - You [NCS Release]
#CompilerDesignByNeso #CompilerDesign #AmbiguityInCFGs

[@yenzyhebron5278]

Hi I'd like to point out that for a grammar to be classified as ambiguous using a parse tree derivation, the grammar has to have either two or more left most parse tree derivation or two or more right most parse derivation for the same input string.
Please don't leave this out. Specify if your parse true will only do leftmost derivation or rightmost derivation.

[@年知ろはると]

hello I have a question:
5:37 the parse tree at the right doesnt seem acceptable since at the left tree he started from 'a' input but at the right tree he started with the 'b' input (and in predictive parsing you can't really advance then backtrack), so aren't they completely different trees?
and if that's the case is G1 actually not ambiguous? please correct me if i'm wrong

[@iosifpuha6114]

Hello, I just don't understand a thing: you said that to determine if a grammar is unambiguous or not is an undecidable problem, so there's no concrete approach/algorithm to do that but then you proceeded to prove that that grammar is ambiguous, using the ()()() string, how did you come up with that? I mean, how should I know what string to use in order to make it work?

[@legityash]

By practicing, just like we do in Trigonometry.

[@josemarichan1183]

Determining if a grammar can be ambiguous is undecidable. We have no concrete method or algorithm for that because there are infinite possible inputs. However, when we are given a particular input, determining ambiguity for that is now decidable/solvable.

[@年知ろはると]

i'm sorry, please correct me if i'm wrong @NesoAcademy
but on 5:37 the parse tree at the right doesnt seem acceptable since at the left tree you started from 'a' input but at the right tree you started with the 'b' input (and in predictive parsing you can't really advance then backtrack), so aren't they completely different trees?
and if that's really the case then G1 isn't ambiguous.

[@eminence_Shadow]

How did you know what to derive??

[@854Rri]

Just generate any input from the grammar and test it

[@ritvikupadhyay4677]

@@854Rri but what if the input that i generate doesnt necessarily have another way to derive it?

[@IlIIlIIlIlIlIIlIIlI]

@upadhyay4677 I don't know if I understand it right, but you have to test another input then. Till you are sure (or can prove) that it is ambiguous or not

[@princenedjoh]

You would have to generate it using the set of terminals given

[@kaselunt472]

Thanks for this extremely well-made content, you are a lifesaver! Quick question: how did you decide what strings to test with?
You used ababa, and then ab. Just wondering if those were given with the question or if you chose them somehow. Thanks again!

[@rajeshprajapati6662]

You just start with something and in the process of generation you will get some strings. Take them and try to make two parse trees. I solved like this both questions on my own. Thanks to him. It is not necessary to have strings in the beginning.

[@derriekxavier]

at 3:33, how is it ambigous when both trees are the same and have the same result?

[@rajeshprajapati6662]

How both trees are same ? they are different for the same expression. See his lectures carefully, he has already explained your answer in previous videos.

[@arjungaming2706]

Sir your lectures are awesome and with easy explanation sir can you uplode more lectures plzzz

[@monicabattacharya6416]

Thank you so much for uploading this video sir 😊🙏🙏🙏.

[@soomaaliga_xalaasha_ah]

4:46 if not given how would you come up with 'ababa' ?

[@BaHuynh-rs5lj]

same )) how you know ababa ? and where is that ?. How about I come with "a". S -> a (only 1 tree, then it is not ambigous?). Other hand, If the grammar too complex or like 1000 rules. How we know the string like "ababa" ?

[@riyansh3396]

At 5:57 you have made 2 parse tree one is left most and another is right most, so how can it be Ambiguous Grammar

[@IlIIlIIlIlIlIIlIIlI]

A Context Free Grammar is ambiguous, when to every word only one derivation tree exists. The derivation trees of left most and right most are different, so it is ambiguous. It also follows that either left most or right most derivation has ambiguous trees. This is also noticeable in the trees shown, because both trees could be derived from a left most derivation.

[@killMan5746]

yeah hes wrong

[@年知ろはると]

@@IlIIlIIlIlIlIIlIIlI i don't get it, can you dumb it down for me? xD

[@marvel_ethio-k4p]

since it is a question,so how you take the strings ababa and ab

[@none9304]

1:55 ahh yes SS :) iykuk

[@monicabattacharya6416]

To take your payment course , it's asking GST.
What we have to enter?
Please reply sir 😊

[@nesoacademy]

Hello, you can leave this field empty. It is for the people/company having a GST Number.

[@monicabattacharya6416]

@@nesoacademy what is GST number?

[@rajeshprajapati6662]

@@monicabattacharya6416 GSTIN, short for Goods and Services Tax Identification Number, is a unique 15 digit identification number assigned to every taxpayer (primarily dealer or supplier or any business entity) registered under the GST regime.

[@sakshijadhav6394]

what is string for Q1 ?

[@sakshijadhav6394]

3 parenthesis or anything else ?????

[@princenedjoh]

3 pairs of parentheses

[@harshithashetty233]

Can u share the link of queue in data structure

[@nesoacademy]

www.nesoacademy.org/cs/01-data-structures/07-queues/01-basics-of-queues

[@harshithashetty233]

Thank you

[@harshithashetty233]

We should pay for that?

[@rajeshprajapati1851]

@@harshithashetty233 yes ! Subscription