Pumping Lemma for Context-Free Languages: Four Examples

Поделиться
HTML-код
  • Опубликовано: 24 ноя 2024

Комментарии • 99

  • @EasyTheory
    @EasyTheory  4 года назад +10

    Timestamps:
    0:00 - Intro
    1:00 - Main steps in proofs
    3:30 - {a^n b^n c^n : n at least 0}
    14:20 - {a^i b^j c^k : i at most j, j at most k}
    24:00 - {ww : w in {0,1}*}
    37:30 - {w in {a,b,c,d}* : w has more c's than a's, b's, or d's}

    • @manikantaalapati7726
      @manikantaalapati7726 Год назад

      In the last example, we can pump down either C's or a's
      If we pump down a's, the resultant string is still in the language
      Can you please explain this?

    • @jiazhengrobert8698
      @jiazhengrobert8698 11 месяцев назад

      ​@@manikantaalapati7726I think in the case where v is empty and y contains a, in this case we have to pump up instead of pumping down.

  • @theguitarist1290
    @theguitarist1290 3 года назад +82

    Watching this with 7 hrs to go until my theory of computation midterm. You definitely help clear things up, keep it up!

  • @joeyl9394
    @joeyl9394 4 года назад +31

    you really put a lot of work into the channel. nothing but respect for you my friend :)

  • @micahnettey4944
    @micahnettey4944 Год назад +17

    This is probably the best explanation I've seen on RUclips. Most other videos don't make it generalized, they use specific string lengths rather than sticking to general string lengths. Glad I found this simple explanation. Got a sub from me.

  • @NotFlame
    @NotFlame 2 года назад +5

    This channel deserves much more, looking at the time and effort you put in the video tysm!

  • @benganot4363
    @benganot4363 3 года назад +7

    Your content and explanation are simply good on a level that cannot be described in words. You make a theoretical material that usually breaks the teeth of computer science students seem so obvious and simple to understand, not to mention beautiful.

  • @jessif.
    @jessif. Год назад +1

    Thank you. I like the writing board and colors you use, it makes it more enjoyable to watch. Your explanations are easy to understand.

  • @arivan5722
    @arivan5722 14 дней назад

    Thanks for the video, this is one of the clearest explanations I've seen yet. I was having some trouble understanding the exact intuition from my textbook alone.

  • @33x44y
    @33x44y 4 месяца назад

    i was reading my notes from my lecture on this topic and had a really tough time understanding it. this cleared things up for me perfectly. thanks sir, youre a life saver.

  • @Kidpunk98
    @Kidpunk98 3 года назад +4

    Thank you so much for this. Perfectly explained, adn you caught every details and edge case and made sure to explain it in simple terms. So grateful!

  • @almasanchez4538
    @almasanchez4538 Год назад +2

    I really want to thank you because after watching your videos and your explanations, I'm able to explain better all the exercises (I'm assistant professor of theory of computation in Mexico ) 💜💜💜

  • @user-dj9iu2et3r
    @user-dj9iu2et3r Год назад +1

    This is a wonderful video. Both of your pumping lemma examples videos helped me massively.

  • @nawdawg4300
    @nawdawg4300 2 месяца назад

    Took this material 4 years ago and now for the graduate version of this my professor is giving us a 20% prereq test the second week of class. Great video I'm sure it will improve my grade.

  • @shlokkulkarni5777
    @shlokkulkarni5777 Месяц назад

    Nicely done. Very interesting topic and I have found it extremely difficult to find a good video on it and this is certainly a great one. Thanks.

  • @sanjeevpenupala
    @sanjeevpenupala 3 года назад +5

    This is such a underrated channel. This needs more views and likes for the type of conent you have, sir! Really amazing stuff!

  • @onepiecefan3969
    @onepiecefan3969 8 месяцев назад +5

    On the last example where you try to pump down c's and a's to make #c's

  • @martin_skachkov6016
    @martin_skachkov6016 2 года назад +5

    Those videos are really helpful, thank you so much :) ! Will you consider making more proofs of context free languages like this one?

  • @AbbasKhan-pd6ke
    @AbbasKhan-pd6ke 6 месяцев назад

    Easily the best Pumping Lemma lecture .... Thank you so much 😇🎉

  • @thaoho7176
    @thaoho7176 3 года назад +1

    It helps clear things up a lot. Thank you so much!

  • @Ale-hh1xz
    @Ale-hh1xz Год назад

    Crazy good explanation, thanks a lot man

  • @bentleyjiminybobzongynong8522
    @bentleyjiminybobzongynong8522 Год назад

    Love your videos, my friend is able to self study this subject with them

  • @Xavier_Wells
    @Xavier_Wells 2 года назад

    This really clarified things for me, thanks!

  • @euphemiaw.2175
    @euphemiaw.2175 2 года назад

    So helpful. Thank you so much! Love all your videos!

  • @fatalhasse
    @fatalhasse 3 года назад +1

    Thank you so much for the great content! Learning a lot from you. Subbed

    • @EasyTheory
      @EasyTheory  3 года назад

      Of course, thank you for subbing!

  • @48_subhambanerjee22
    @48_subhambanerjee22 5 месяцев назад +1

    ❤❤❤❤❤❤❤ CS IS LOVE... I BLEED CS

  • @carolinarojano7298
    @carolinarojano7298 2 года назад

    You really made me understand, nice way of teaching. keep it up

  • @xGeicher
    @xGeicher 3 года назад +1

    this was brilliant

  • @Rglezy
    @Rglezy 3 года назад +1

    You are the real mvp.

  • @satyamjha68
    @satyamjha68 8 месяцев назад

    You teach really well!! Thank you!

  • @what8212
    @what8212 Месяц назад

    youre the goat thank you

  • @anonim5052
    @anonim5052 2 дня назад

    You are literally carrying my master degree

  • @caribreeze
    @caribreeze 3 года назад

    helped me a ton with understanding my hw! thank you!

  • @iskerop
    @iskerop 3 года назад +1

    great video, thank you!

  • @RoughRoman
    @RoughRoman 3 года назад

    This is really good thanks

  • @markhettwer8219
    @markhettwer8219 3 года назад

    I had the garbage truck show up on my street at the same time loool. Great video, really helpful!

  • @CodingAhead
    @CodingAhead Год назад +1

    he is GOAT

  • @ferhatkorkmaz11
    @ferhatkorkmaz11 Год назад

    great content thank you a lot

  • @strychnotic3933
    @strychnotic3933 3 года назад

    tremendous !!!

  • @surferriness
    @surferriness Год назад

    I fkn love you man

  • @orestisiona6697
    @orestisiona6697 Год назад

    Great video thank you. A small correction tho, you are saying that in case we only had a language of only ab instead of abc with the pumping lemma we can show that ab is CFL. This is actually false, although it is a CFL, the pumping lemma is not proof that it is (it only works the other way around, it is sound but not complete).

  • @superdahoho
    @superdahoho 3 года назад

    I think the tricky part is here to find all cases and prove there's some i that breaks out of the language.
    on exams, i just don't have enough time to find and write proofs for all of them :(

    • @EasyTheory
      @EasyTheory  3 года назад +5

      Yes that's an art, not a science. I wish I could give a specific reason how to do these, but there just isn't a way in general. A good tip is to look at patterns of the strings in the language, and be "right on the edge" of being out of the language, but not there yet, and having the pumping allow yourself to pump out.

  • @ewoudvanuijthoven4245
    @ewoudvanuijthoven4245 3 года назад

    saving my exam next week :)))

  • @Mahsun23
    @Mahsun23 Год назад

    Thnx dude

  • @KartikayKaul
    @KartikayKaul Год назад

    Pump up the jam, pump it up is a nice song for pumping lemmas xD 43:16

  • @CP-mg5ws
    @CP-mg5ws 3 года назад +1

    why doesn't pumping with i=0 work for the first problem? Surely that removes an a from the word making the number of a's less than the number of b's and c's?

  • @razvanefros411
    @razvanefros411 Год назад

    one thing I struggle with when constructing a proof with pumping lemma is the depth of the explanation you have to go for. At what point does it become obvious enough?
    for example, at 31:00 he builds an argument about the midpoint shifting, and the first characters of the 2 halves being different from each other. I found it obvious enough that when V and Y are in the same half, pumping it will make that half longer/shorter, and therefore different from the other half. Is my line of thought not good enough?

  • @caleb5688
    @caleb5688 Год назад +1

    For the last example, how do you know that the last case must have at least one occurrence of c? Isn't it possible that v is the empty string and y is all a's? Thanks!

    • @bilalfellah1003
      @bilalfellah1003 6 месяцев назад +1

      if you happen to know the answer of your question, share it pls bcz i have the same question

  • @felipeperessim9069
    @felipeperessim9069 4 года назад +3

    In the proof, is it necessary to consider all the possible cases or considering just a single one is enough?

    • @EasyTheory
      @EasyTheory  4 года назад +2

      I address this in the video. You do need to consider all possible decompositions. If you don't do this, then for some decomposition that you "don't consider", that might be the one that allows w to be pumped and always "stay in" the language.

    • @ashurajput3526
      @ashurajput3526 9 дней назад

      @@EasyTheory and if even in one case the pumping gives a valid result then will it be considered as CFL ?
      i mean a^nb^n only becomes CFL when v and y have same number of a and b to be pumped , in rather all the cases it fails to be a CFL . so all the cases must be false for a language to be not CFl , else even if one generates a valid one , then it is CFL.
      Please tell sir.

  • @rashmiprabhubhaipatel5359
    @rashmiprabhubhaipatel5359 2 года назад

    Could you please solve this? a^k b^j | k>(j-1)^2

  • @kasperwesteraa9558
    @kasperwesteraa9558 3 года назад +1

    Thank you for your great videos! I have a question: Why do we have to go through EVERY case of w's subdivision? Isn't it enough just to find ONE i, for which we pump out of the language? Cheers, Kasper

    • @juanbomfim22
      @juanbomfim22 3 года назад

      Because the lemma states if one language is CFL then exists a pumping length p that satisfies properties. So you go through each case in order to find this p and you wont find any if the language is not CFL

  • @nothingatall6882
    @nothingatall6882 2 месяца назад

    For 0^p1^p0^p1^p why couldn't v be in some partition of the first 0 and 1 and x is in the middle and y be the same length partition of the second 0 and 1 and then u can pump the v and y and get = nums

  • @andrewrover126
    @andrewrover126 Год назад

    For case 1 of the last example wouldn't the number of c's be less than not only the a's, but the b's and d's as well? a, b, and d are all to the power of p. So if we remove at least one p from c, then all of those no longer have a greater number of their respective letter individually, than the number of c's?

  • @joelton4167
    @joelton4167 Год назад

    struggling buggling juggling tuggling

  • @sanjeevpenupala
    @sanjeevpenupala 3 года назад

    What program are you using to write your problems down?

  • @monkebythesea6756
    @monkebythesea6756 5 месяцев назад

    BİLEN BİLİR BÜYÜK BAŞKAN HİNDULARA BENZMEEZSIN SANA 302İ GEÇEYİMBİ TEPSİ BAKALVA ALICAM BUYUK USTAD SAYGILAR ABI

  • @riebeck1986
    @riebeck1986 2 года назад

    If a language is context free, then does it always satisfy pumping lemma? For example in a^nb^nc^m, m != n it is context free. But if I apply pumping lemma on it, lets say on the string a^pb^pc^(p+1), then it does not satify pumping lemma in some cases. Can anyone shed some light on this? I am confused.

  • @charactername263
    @charactername263 2 года назад

    23:16 Why cant vxy span a,b and c? Is it correct to state that for any pump length P a span vxy to include a,b,c must have |vxy| >= p+2 (p bs 1 a 1 c) yet |vxy|

  • @blackjesus6333
    @blackjesus6333 2 месяца назад +1

    why did you put the girl in the thumbnail lmao

  • @razvanefros411
    @razvanefros411 Год назад

    On the 4th language, Case 4, if we have V in the string of C's and Y in the string of A's, and we know that |vy| >0, we could definitely say that V=empty string, so when pumping down to i=0, the number of C's doesnt change, therefore the word stays in the language. Or am I missing something?

    • @Uzumaki_Naruto061
      @Uzumaki_Naruto061 Год назад

      Yes, he missed that case, in that case, you pump up which increases the #a's which becomes more than #c's

    • @alifuatdundar194
      @alifuatdundar194 10 месяцев назад

      @@Uzumaki_Naruto061 this state already was evaulated in case 2, isn't it?

  • @Felix_leee
    @Felix_leee 5 месяцев назад

    in the last example, in the first case, how can v and y be only in C's. The numbers of C's is p+1 but shouldnt |vxy|

    • @yuricolangelo6688
      @yuricolangelo6688 5 месяцев назад

      I guess because the string is originally decomposed in uvxyz, the number of c's is p+1, so to fit into vxy you can put that +1 c into u (the substring before vxy)

    • @Felix_leee
      @Felix_leee 5 месяцев назад

      @@yuricolangelo6688yeah I didn’t think that was possible at the moment but then I realized we could. Thank you

  • @farouksabry
    @farouksabry 3 года назад

    I have a problem in the last example when it could be Cs or As. When we pump down to i=0 we dont know if the Cs will decrease through the V or the As through the Y. If its the As only doesn't this make it valid?

    • @EasyTheory
      @EasyTheory  3 года назад +2

      Not only that, it could be that either V or Y have both a C or an A in one of them. If it is the case that VY together has C and A, pump down. No matter what, C cannot be the most frequent character anymore, and we are done.
      If it was As only, pump up.

  • @koraykara6270
    @koraykara6270 3 года назад

    In the last question, for the case4, we can think that v is empty and y contains some a's . Then what if we pump down to i=0 ? That concludes that we have more number of c's than a's, b's and d's. and it is actually OK am I wrong?

    • @jackmccarthy7644
      @jackmccarthy7644 3 года назад

      If v is empty and y contains some a's, then we could just as easily pump up to i=2, which would cause the number of a's to be greater then the number of c's, putting the string outside of the language.
      He should have mentioned this possible case in his proof, but it still works once you think about it.

    • @GDX17
      @GDX17 2 года назад

      @@jackmccarthy7644 that falls under case 2

  • @sskylark_
    @sskylark_ 3 года назад +1

    Wish I could transfer you my tuition money

    • @EasyTheory
      @EasyTheory  3 года назад

      My name is Sallie Mae now...

  • @LosEspookys
    @LosEspookys 3 года назад

    For the first problem, why can't vxy be in both a,b, and c?

    • @bushvatoi
      @bushvatoi 3 года назад

      I have a similar question regarding the problem 2 {a^i b^j c^k : i at most j, j at most k} . And why we don't consider v and y are all a's and c's?

    • @sanjeevpenupala
      @sanjeevpenupala 3 года назад +4

      The reason is that one of the conditions of pumping lemma is that |vxy|

    • @abigarcia9588
      @abigarcia9588 7 месяцев назад

      @@sanjeevpenupala ohh tysm hahah the doubt was killing me and finally i get it

  • @user-br2dw8no4r
    @user-br2dw8no4r 3 года назад +1

    When you clickbait people into learning

  • @nitsuj1001
    @nitsuj1001 2 года назад

    wheres the girl from the thumbnail?

    • @cp65143
      @cp65143 2 года назад

      🙄🙄🙄

  • @mubelesihanyumbu92
    @mubelesihanyumbu92 5 месяцев назад

    You’ve earned me my cs degree 🫶🏿

  • @Minecraft-tt2ep
    @Minecraft-tt2ep Год назад

    poor w, what did it do to get kicked out of uvxyz?

  • @vankey9685
    @vankey9685 Год назад

    can u prove that L = {w ∈ {a, b, c}* | (numers of a's and b's are equal and number of c's is greater than number of a's)} is Context-Free ? pls help!