date: 2024-10-30
title: 05-TOC-Pumping Lemma
status: DONE
author:
- AllenYGY
tags:
- NOTE
- TOC
- Pumping-Lemma
publish: True
TOC-Pumping Lemma
If
p is the pumping length.
Instead of proving the lemma formally, let's try to understand it.
Assume
Let
Assume
To accept
By pigeonhole principle, some states
Assuming
Then, it's trivial that
The pumping lemma is used to prove a language is not regular.
To prove the language
Proof:
Assume
If
If
If
In summary,
Here are some notes.
The pumping length
But the pumping lemma is "machine independent". Thus you cannot assume the value of
The condition
Otherwise,
The condition
The pumping lemma is only a necessary condition for regular.
It is not a sufficient condition.
In other words, if you cannot find a
Answer: Not regular.
Proof:
Assume
Since prime numbers are infinite,
By the pumping lemma,
Here,
Now, consider the string
However,
Thus,
Answer: Not regular.
Proof (Sketch):
We can express
If
However, this contradicts the result from
Thus,
Answer: Regular. In fact,
Proof:
Consider
Case 0: If
Case 1: If
Case 2: If
Thus,
Answer: Regular.
Answer: Not regular.
Proof (Sketch):
If
Assume L is context-free. Let
By the pumping lemma,
vxy
before the #
vxy
before the #
more 1's but less 0's