I think he just skipped the explanation, there are actually 3 possible cases for y (and thus xy). 1) y contains only 0s, in which case a second time through will result in more 0s in the word 2) y contains only 1s, in which case a second time through will result in more 1s in the word 3) y contains both 0s and 1s (number of each isn't important), in which case a second time through will results in some 1s being amongst the 0s (like say y=01 and our word is 000111, a second time through would result in 00010111, which isn't a valid word).
Dr. Gusfield is a true educator. He has posted many other lecture videos of his on his website. Any one interested should check it out at web.cs.ucdavis.edu/~gusfield/
Well, some languages (i.e. rules that define if some string is a part of the language or not) that have some nice properties are called regular. It's extremely easy to write parsers (i.e. programs that analyze syntax) or programs that tell if some string is a part of the language for such languages. Pumping lemma is a lemma that can be used to easily show, that a language is not regular. And lastly, context-free languages are broader group of languages (all regular languages are context-free) that is still relatively easy to recognize or parse. For example, almost all programming languages are context-free. This course, as far as I know, is made for software engineers, and if you are one, than that is the easiest way to describe what a context-free language is: it is a language describable by BNF.
Introduction to CFLs start at 1:00:18 if anyone's interested
Pd: Great lectures, watched the entire playlist till now
Thank you Professor! You've shown a very instructive material. Can you provide the course website that you've mentioned? Thank you
CFG is such a tough subject to master.
if i = 0 then size y is 0 and the pumping lemma is automatically contradicted. Shouldn't i be >0 not >=0?
+South Pa I would assume that 'i' does not have anything to do with the size of 'y' but relates to the number of y's.
Thank you sir ... I have learnt a lot
at 3:37, I don't understand why xy just contains 0.
I think he just skipped the explanation, there are actually 3 possible cases for y (and thus xy).
1) y contains only 0s, in which case a second time through will result in more 0s in the word
2) y contains only 1s, in which case a second time through will result in more 1s in the word
3) y contains both 0s and 1s (number of each isn't important), in which case a second time through will results in some 1s being amongst the 0s (like say y=01 and our word is 000111, a second time through would result in 00010111, which isn't a valid word).
drewbudd thank you so much, now I got this Pumping Lemma proof
1:00:25 Jump to CFLs
Thank you ...
Dr. Gusfield is a true educator. He has posted many other lecture videos of his on his website. Any one interested should check it out at
web.cs.ucdavis.edu/~gusfield/
How would you explain to a layman what the subject discussed here is all about? Who dares the challenge?
Well, some languages (i.e. rules that define if some string is a part of the language or not) that have some nice properties are called regular. It's extremely easy to write parsers (i.e. programs that analyze syntax) or programs that tell if some string is a part of the language for such languages.
Pumping lemma is a lemma that can be used to easily show, that a language is not regular.
And lastly, context-free languages are broader group of languages (all regular languages are context-free) that is still relatively easy to recognize or parse. For example, almost all programming languages are context-free.
This course, as far as I know, is made for software engineers, and if you are one, than that is the easiest way to describe what a context-free language is: it is a language describable by BNF.