Pumping Lemma for Regular Languages FOUR Examples and Proof Strategies!
45.4 هزار بار بازدید -
4 سال پیش
-
Here we do four proofs
Here we do four proofs of languages not being regular using the pumping lemma for regular languages, as well as give a proof strategy. The basic idea is to suppose that the language is indeed regular. Then the lemma asserts that a pumping constant "p" for that language exists. Then pick a string (chosen carefully) that is in the language and of length at least p. After observing all possible decompositions of that string into three pieces x, y, z (according to the rules), we choose a value of i such that xy^iz is not in the language. The video about the pumping lemma's proof is here: Pumping Lemma for Regular Languages F....
We do four different languages by showing slightly different variations on the theme of proof outlined above, shown in the chapters below:
0:00 - Introduction
1:30 - General Proof Strategy
7:05 - {0^n 1^n : n at least 0}
17:22 - {0^i 1^j : i strictly larger than j}
25:18 - {0^n : n is a perfect square}
34:18 - {0^n : n is a prime number}
44:56 - Conclusion
If you like this content, please consider subscribing to my channel: @easytheory
▶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.
We do four different languages by showing slightly different variations on the theme of proof outlined above, shown in the chapters below:
0:00 - Introduction
1:30 - General Proof Strategy
7:05 - {0^n 1^n : n at least 0}
17:22 - {0^i 1^j : i strictly larger than j}
25:18 - {0^n : n is a perfect square}
34:18 - {0^n : n is a prime number}
44:56 - Conclusion
If you like this content, please consider subscribing to my channel: @easytheory
▶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/21 منتشر شده
است.
45,461
بـار بازدید شده