Context-Free Grammar Definitions: Yields, Ambiguous, Leftmost Derivation

Here we are doing a bonus video about context-free grammars (CFGs): yields, ambiguous, and leftmost derivation. They will all be important in upcoming videos. Yields involves the application of a single rule, and a derivation is a sequence of yields operations to yield a string that is only consisting of terminals. A leftmost derivation is one where the leftmost variable is always the one that is replaced. Ambiguous grammars are those that have some string they make that has 2 different leftmost derivations. A language is inherently ambiguous if every CFG for it is ambiguous.
Donation (appears on streams): streamlabs.com...
Paypal: paypal.me/easy...
Patreon: / easytheory
Discord: / discord
#easytheory #gate #theory
TH-cam Live Streaming (Sundays) - subscribe for when these occur.
Social Media:
Facebook Page: / easytheory
Facebook group: / easytheory
Twitter: / easytheory
Merch:
Language Hierarchy Apparel: teespring.com/...
Pumping Lemma Apparel: teespring.com/...
If you like this content, please consider subscribing to my channel: / @easytheory
Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy
▶SEND ME THEORY QUESTIONS◀
[e-mail]
▶ABOUT ME◀
I am a professor of Computer Science, and am passionate about CS theory. I have taught many courses at several different universities, including several sections of undergraduate and graduate theory-level classes.

[@umairphoenix]

Man Seriously You Deserve Lot of appreciation for your work!

[@havensmith6374]

Thank you!! you are why I am passing computational theory

[@hyunhokim7572]

This is awesome content. actually saved my life.

[@vimalathithand917]

Thanks! Really got insights ,a great video !

[@kostastsaousis7445]

You're gonna shine one day proffesor!

[@stijnjongbloed1]

Thanks for the video!

[@shaii1172]

Thank you! that was really helpful !

[@3e815]

Great video!! i clicked on this video because of the thumbnail btw.

[@emilyisreading_]

thank you bro

[@skyadav8842]

great work bro

[@jacobh1833]

Is the * in the E set of terminals just mean 'the permutation/combinations of all elements in the set E' or does it have a more nuanced definition?

[@samjudelson]

thanks!

[@constantmackin]

Hi, the two examples you shared for left most derivations, in the first example when you have replaced S with epsilon only, how is that a leftmost derivation when you've merely used a rule? The second makes sense that you've replaced the left most variable with a epsilon. Please help

[@itsmemouha2811]

Hey! Nice vid. Could you make a video explaining reductions in a deterministic CFG? I find it very hard to understand

[@EasyTheory]

What do you mean by reduction?

[@itsmemouha2811]

@@EasyTheory the bottom up derivation. In Sipser, a DCFG is defined by a series of reduction from a string of all terminal to the start variable.

[@EasyTheory]

@@itsmemouha2811 Didn't know about that! Got some reading to do 👀

[@techademy9354]

In Ambiguous, the derivation has to have the same answer?

[@tomasnascimento1762]

yes, It must result in the same final string

[@vishalmenon9027]

for the second derivation you did for S -> SS | ε, why is this considered leftmost derivation because aren't we still replacing the S on the right? I thought leftmost derivation means you only replace leftmost variables, but once you have done that, are you allowed to replace another variable that is not the leftmost one?
Edit: Is it because we cannot end on a variable so we need to replace the right one?

[@fallonboone487]

I might misunderstand your question and my answer may be off ( i am learning as well). But, with a leftmost derivation you start with variables to the left and replace them moving left->right until the string is in the set of terminals. You don't just replace the leftmost variable. If you only replaced the leftmost variable and there were other variables in the string, the derivation would be incomplete. Does this answer the question?