Pumping Lemma for Regular Languages FULL PROOF

Easy Theory
Easy Theory
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.
4 سال پیش در تاریخ 1399/06/14 منتشر شده است.
20,389 بـار بازدید شده
... بیشتر