Nonregular languages: How to use the Pumping Lemma

Опубликовано: 05 Ноябрь 2020
на канале: lydia

86,696

3.2k

We know that all regular languages must satisfy the pumping lemma. This means we can use the pumping lemma to prove that a language is NOT regular by showing that it does NOT satisfy the pumping lemma.

This video provides a little more intuition for how such a proof works.

If you aren't yet familiar with what exactly the pumping lemma is, check this video out first: • What is the Pumping Lemma

____________________
Additional resources:

Michael Sipser. 2006. Introduction to the Theory of Computation (2nd. ed.). International Thomson Publishing.
The main source of my Theory of Computation knowledge (a textbook). Read Chapter 1.4: Nonregular Languages to learn more about the pumping lemma and examples of the formal proofs.
_____________________

And as always, this video project could not have been done without the support and guidance of Audrey St. John at Mount Holyoke College, a truly incredible professor-mentor-human.

Смотрите видео Nonregular languages: How to use the Pumping Lemma онлайн без регистрации, длительностью часов минут секунд в хорошем качестве. Это видео добавил пользователь lydia 05 Ноябрь 2020, не забудьте поделиться им ссылкой с друзьями и знакомыми, на нашем сайте его посмотрели 86,69 раз и оно понравилось 3.2 тысяч людям.

5,24