Pumping Lemma for Regular Languages FULL PROOF
20.3 هزار بار بازدید -
4 سال پیش
-
Here we give a proof
Here we give a proof of the pumping lemma for regular languages, one of the most important results in the entire class. The idea stems from what we did last time, in that we can prove that "other" strings exist in a given language provided that it is regular. We classify what those other strings' properties must have, and criteria in order to use the pumping lemma. It isn't useful in that it cannot help us prove that languages are regular, but it will help in proving languages are not regular.
#easytheory #gate #theory
Chapters:
0:00 - Introduction
1:30 - Can we guarantee a loop?
4:00 - Strings of length n see n+1 states
7:55 - Pumping Lemma statement
15:00 - Three properties of the Pumping Lemma
Contribute:
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: Patreon: easytheory
Discord: Discord: discord
Youtube Live Streaming (Sundays) - subscribe for when these occur.
Social Media:
Facebook Page: Facebook: easytheory
Facebook group: Facebook: easytheory
Twitter: Twitter: EasyTheory
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierar...
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-f...
If you like this content, please consider subscribing to my channel: @easytheory
Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy
▶SEND ME THEORY QUESTIONS◀
[email protected]
▶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.
#easytheory #gate #theory
Chapters:
0:00 - Introduction
1:30 - Can we guarantee a loop?
4:00 - Strings of length n see n+1 states
7:55 - Pumping Lemma statement
15:00 - Three properties of the Pumping Lemma
Contribute:
Donation (appears on streams): https://streamlabs.com/easytheory1/tip
Paypal: https://paypal.me/easytheory
Patreon: Patreon: easytheory
Discord: Discord: discord
Youtube Live Streaming (Sundays) - subscribe for when these occur.
Social Media:
Facebook Page: Facebook: easytheory
Facebook group: Facebook: easytheory
Twitter: Twitter: EasyTheory
Merch:
Language Hierarchy Apparel: https://teespring.com/language-hierar...
Pumping Lemma Apparel: https://teespring.com/pumping-lemma-f...
If you like this content, please consider subscribing to my channel: @easytheory
Gold Supporters: Micah Wood
Silver Supporters: Timmy Gy
▶SEND ME THEORY QUESTIONS◀
[email protected]
▶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.
4 سال پیش
در تاریخ 1399/06/14 منتشر شده
است.
20,389
بـار بازدید شده