A context-free grammar G is said to be ambiguous if there exists some w ∈ L (G) that has at least two distinct derivation trees. Alternatively, ambiguity implies the existence of two or more leftmost or rightmost derivations. Introduction To Formal Languages And Automata, 6 Edition Peter Linz
A grammar that has more than one rightmost derivation for some string in the language generated by the grammar is called a right-recursive grammar. Right-recursive grammars are not necessarily ambiguous
Now I am preparing lecture notes using your lectures from beginning..I will finish the whole toc lectures in few more days..I will score better marks for toc exam❤️
Basically if anyone still finds ambiguous questions hard to solve just remember that prove that question through both right most deviations and left most deviations
Suppose that two parse trees has the same root as well as starting inputs and then they differ does that make the grammar ambiguous or not ? For example If S-> aB | bA And if both the parse trees derive starts with aB but from 2nd input they differ then the grammar become ambiguous or not ? Or both the parse trees must have different strat as one parse trees start with input aB, then another must start with bA Then only the grammar become ambiguous
No , here the + and * are not treated as operators , they are just terminal symbols like a and b so (s+s) * s will be just s + s * s , don't open the parenthesis like operators but like normal symbols as in --- (s a s ) b s == s a s b s
tomorrow is my paper of TOC i learnt so many things from your videos.. but pushdown automata and turing machine..is not in your 77 videos.. but anyway THANKYOU SIR...
Suppose that two parse trees has the same root as well as starting inputs and then they differ does that make the grammar ambiguous or not ? For example If S-> aB | bA And if both the parse trees derive starts with aB but from 2nd input they differ then the grammar become ambiguous or not ? Or both the parse trees must have different strat as one parse trees start with input aB, then another must start with bA Then only the grammar become ambiguous
in our country only thing we know about india is bollywood but now as a computer engineering student i would say big respect for you and i would FAİL all my exams if not you and another indian channels F
hi, very interesting lectures ! i had an subject 'formal languages and compilation methods' and we had a exercise on the exam : we had a grammar and we had to check if this language is ambigous . How to do It ?
Suraj Bhatt Instead start with S+S and replace first S with S*S , then u have S*S + S, now out a,b appropriately. Hope it helps u out cuz Sir did a mistake in the video
What if we are not given a string but only a grammar. How would we go about trying to find a string that can be obtained by two different left derivation trees?
can any body help me? A grammar has the following productions: S --> aSSb | a | bSa Which of the following sentences are in the language that is generated by this grammar? a) aabbaabb b) aaaaabb c) bbbaabbaa d) none of the answers above are correct
In the ambiguity video by @gatesmasher, he mentions that whether it's LMD or RMD, if we obtain two derivation trees simultaneously, it is considered ambiguous. However, in your lecture, you assert that it should be only LMD with two derivation trees. Now, I am confused about whose perspective is accurate - yours or gatesmasher's.
Yes a language is ambiguous if it can generate at-least one sentence from two left most derivation or two right most derivation. The following statements are equivalent. • A CFG is ambiguous if some sentence it generates has more than one derivation tree • A CFG is ambiguous if there is a some sentence it generates with more than one left-most derivation • A CFG is ambiguous if there is a some sentence it generates with more than one right-most derivation
A context-free grammar G is said to be ambiguous if there exists some w ∈ L (G) that has at least two distinct derivation trees. Alternatively, ambiguity implies the existence of two or more leftmost or rightmost derivations.
Introduction To Formal Languages And Automata, 6 Edition
Peter Linz
oho guruji. video me to kuch aur hi btaya hai
A grammar that has more than one rightmost derivation for some string in the language generated by the grammar is called a right-recursive grammar. Right-recursive grammars are not necessarily ambiguous
SRM se ho?
Video me right derivation tree ke baare me nahi mention kiya hai.
@@humaneBicycle
@@humaneBicyclegawar ho kya? English padhna nhi aata?
Now I am preparing lecture notes using your lectures from beginning..I will finish the whole toc lectures in few more days..I will score better marks for toc exam❤️
me too
G: S iEtSeS|iEtS|a, E b|c|d please answer this question
Pls share notes
How much did u get 😀
I have started it today and completed it today and tommorrow is my exam
Sir please mention this also as a note that language with two or more right derivation for same sentence is also ambiguous.
i think it's a trivial and redundant conclusion.
Yes either more than one right most derivation tree or left most derivation tree
left or right doesn't matter, the two derivations just need to have the same structure.
Basically if anyone still finds ambiguous questions hard to solve just remember that prove that question through both right most deviations and left most deviations
If one is built on left derivation and other is right derivation, can we say it is ambiguous.. ??
@@naveenkumargembali3494yes
Nope, you have to derive the string only with the left derivation tree@@naveenkumargembali3494
Suppose that two parse trees has the same root as well as starting inputs and then they differ does that make the grammar ambiguous or not ?
For example
If S-> aB | bA
And if both the parse trees derive starts with aB but from 2nd input they differ then the grammar become ambiguous or not ?
Or both the parse trees must have different strat as one parse trees start with input aB, then another must start with bA
Then only the grammar become ambiguous
i am watching these videos serially... and this is the best resource available on this topic
You are very good work for providing free toc class
thanks man, i'm studying designing compilers and this a good insight of the ambiguity topic thanks again
Concept is correct but in 2nd line of S--> S*S , I think it should be (S+S)*S = S*S+S*S
yesi feel same
Yes I think 🤔.u r right
No , here the + and * are not treated as operators , they are just terminal symbols like a and b
so (s+s) * s will be just s + s * s ,
don't open the parenthesis like operators but like normal symbols
as in ---
(s a s ) b s == s a s b s
tomorrow is my paper of TOC i learnt so many things from your videos..
but pushdown automata and turing machine..is not in your 77 videos..
but anyway THANKYOU SIR...
In place of 2 or more derivative tree... simply we can use more than 1 derivations....I think this is very easy to remember
Very helpful 👍Thank you sir !!
I will donate you at the end of my semester for your videos. Thank you isn't enough
Thanks so much sir.next week my toc University exam.your video is my book.more helpfully notes thanks allot
(0+1)*(0+1)01 I have doubt in this sum to change as minimization of DFA please slove this sum sir
Suppose that two parse trees has the same root as well as starting inputs and then they differ does that make the grammar ambiguous or not ?
For example
If S-> aB | bA
And if both the parse trees derive starts with aB but from 2nd input they differ then the grammar become ambiguous or not ?
Or both the parse trees must have different strat as one parse trees start with input aB, then another must start with bA
Then only the grammar become ambiguous
Please make a video converting ambiguous to unambiguous
this is a saviour...!thank you sir!
Yes
Please add more about discrete mathematics
Tysm sir ☺it's really very helpful for me😃 thank u so much
My pleasure
Thank you so much sir
Brilliant Explanation Dear Brother
this series is really amazing . 10Q man
A grammer is said to be ambiguous if there exists two or more derivation tree for a string W.
Some grammars are just like my future: Ambiguous.
Good Explanation
Thanks very well explained.
Sir upload the lecture on communication systems and electromagnetic theory
in our country only thing we know about india is bollywood
but now as a computer engineering student i would say big respect for you and i would FAİL all my exams if not you and another indian channels
F
Hey @neso u havent added the closing brackets at 01:49. Pls re-upload
Yeah bro! @neso RE-UPLOAD pa!
thank u sir, your videos are helpful.
Thank You Sir
Thanks sir!
two or more right-derivation trees is ambiguous too?
Yes, it is
In 2nd tree you first replaced right S with (S*S) which contradicts the rule of LMD, please explain.
@Tech RK u r wrong
we are talking about tree so why we are not making it??
record some lectures about checking if the language is regular or not, about top-down parsing and the opposite.
hello ! can we have a course about push down automata, thanks X)
The grammar in the last lecture was also ambiguous, right ?
there is a mistake, in S*S you have directly written S+S*S but it should be (S+S)*S
@Tech RK really?? is it right method?
What is a+b means in the notation?
hi, very interesting lectures ! i had an subject 'formal languages and compilation methods' and we had a exercise on the exam : we had a grammar and we had to check if this language is ambigous . How to do It ?
Big fan of your work💟
4:25 you write s->s*s -> s+s*s But I think that's should be s->s*s -> (s+s)*s.
really its very useful to me
شکریہ سر
Thank you..
In the question its mentioned as S*S and at 2:42 you mention S into S. Are both the things the same?
Tq so muchh sir
👏 👏👏sir your teaching way is vry easy and understandable.... i really impressed by you ... god bless you🌹🌹 sir and thx
sir please add further topics on these videos
You said in previous video for left d tree we have to expand left most possible alphabet but here you are expanding the right one.. Why?
If one is built on left derivation and other is right derivation, can we say it is ambiguous..
In second tree
S is replaced by (s+s)*s....
s+s*s where did that come from..
Suraj Bhatt Instead start with S+S and replace first S with S*S , then u have S*S + S, now out a,b appropriately. Hope it helps u out cuz Sir did a mistake in the video
thanks sir
derivation tree means parse tree ??
sir please upload feedback amplifier
What if we are not given a string but only a grammar. How would we go about trying to find a string that can be obtained by two different left derivation trees?
Philiey pick an string to demonstrate
thanks a lot sir !
What is two or more right derivation trees
great explanation...thank you!
can any body help me?
A grammar has the following productions: S --> aSSb | a | bSa
Which of the following sentences are in the language that is generated by this grammar?
a) aabbaabb
b) aaaaabb
c) bbbaabbaa
d) none of the answers above are correct
its b)
S -> aSSb
aSSb -> aSaSSbb (S -> aSSb)
aSaSSbb -> aaaSSbb (S -> a)
aaaSSbb -> aaaaSbb (S -> a)
aaaaSbb -> aaaaabb (S -> a)
Sir i have a question what if the example was a+a +b would it then be ambiguous or no?
After watching this lecture I thought why I am paying lakhs in my college
why (s+s)*s is not equal to s*s +s*s instead of s+s*s tommorow is my exam someone plz tell me
In the ambiguity video by @gatesmasher, he mentions that whether it's LMD or RMD, if we obtain two derivation trees simultaneously, it is considered ambiguous. However, in your lecture, you assert that it should be only LMD with two derivation trees. Now, I am confused about whose perspective is accurate - yours or gatesmasher's.
Same issue
good effort
I am more focused on bracket mismatch 1:12 😅😅
how are both derivation trees left? i guess first one was right and second was left.. please explain!!!
That's mine doubt too 😎
1:00 you said 'no' if there is one left and one right., but can it be ambiguous if we get 2 or more right trees? Is that possible?
yes, it is
Yes a language is ambiguous if it can generate at-least one sentence from two left most derivation or two right most derivation. The following statements are equivalent.
• A CFG is ambiguous if some sentence it generates has more than one
derivation tree
• A CFG is ambiguous if there is a some sentence it generates with more
than one left-most derivation
• A CFG is ambiguous if there is a some sentence it generates with more
than one right-most derivation
if there exist multiple right-most or left-most derivation for some string generated from grammar it's ambiguous
hi where can i find more examples
unambiguous?
if only one left derivation tree exists,then its unambiguous
S -> SS+ | SS* | a . Why this grammar is not Ambiguous help me please.
im not able to understand this pls anyone explain i hv toc exam next week......
Tomorrow 😏
i love you
❤❤
0:20
👍👍👍👍👍
Open bob
thank you