What is the Pumping Lemma
Every regular language must satisfy the pumping lemma. The formal statement of the pumping lemma is this:
If A is a regular language, then there is a pumping length p, where if s is any string in A that is at least length p, then s may be divided into 3 pieces, s = xyz, satisfying the following conditions:
1. for each i ≥ 0, xyⁱz ∈ A
2. |y|﹥0
3. |xy| ≤ p
The lemma can be a little tricky to understand at first, and hopefully this video can help with that.
This video only covers the basics of the pumping lemma. If you want to know how the pumping lemma is used to prove that a language is not regular, check out this video instead:
____________________
Additional resources:
• Regular Languages: Deterministic Fini...
My previous video on another property of regular languages—the closure property under the regular operations.
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 the pigeonhole principle (and the formal proofs for showing nonregularity).
_____________________
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.
Watch video What is the Pumping Lemma online without registration, duration hours minute second in high quality. This video was added by user lydia 05 November 2020, don't forget to share it with your friends and acquaintances, it has been viewed on our site 126,95 once and liked it 3.9 thousand people.