date: 2024-10-30
title: 05-TOC-Pumping Lemma
status: DONE
author:
  - AllenYGY
tags:
  - NOTE
  - TOC
  - Pumping-Lemma
publish: True

TOC-Pumping Lemma

Pumping Lemma

Lemma (Pumping Lemma)

If is a regular language, then there is a positive constant such that every string of length at least can be written as satisfying the following conditions

for each
, and
.

p is the pumping length.

Instead of proving the lemma formally, let's try to understand it.

Assume is regular and is the which recognizes .
Let be the number of states in .

Assume in of length .

To accept , goes through a sequence of states

By pigeonhole principle, some states appears multiple times in the sequence.

Assuming , the sequence of states can be

Then, it's trivial that , , , are all in .

The pumping lemma is used to prove a language is not regular.

Proof language is not regular

To prove the language is not regular

Assume that is regular.
Construct a string of length .
Show that no matter how is split into , there is always an such that (contradiction).

Proof Example

Theorem

is not regular.

Proof:

Assume is regular. Let , which is a string in . By the pumping lemma, is in the form . The substring can be of the following three cases.

If only consists of 's, then (pump one more time) has more 's than 's. Thus, .
If only consists of 's, same as case 1.
If has both 's and 's, then 's and 's in are intersecting with each other, which is not in the form of . Thus, .

In summary, can never be split into such that for all . Thus, is not regular.

Here are some notes.

The pumping length depends on the machine. Different machines have different pumping length.

But the pumping lemma is "machine independent". Thus you cannot assume the value of .

The condition ensures that the substring being pumped is not empty.
Otherwise,

The condition ensures that always can be pumped by a machine.

The pumping lemma is only a necessary condition for regular.
It is not a sufficient condition.
In other words, if you cannot find a or such does not exist to accomplish the proof, you CANNOT say the language is regular.

Pumping lemma proof example

.

Answer: Not regular.

Proof:

Assume is regular. Consider the string , where is a prime number and (where is a constant from the pumping lemma). By definition, .

Since prime numbers are infinite, is constructible for some . (This point is crucial because, if were not constructible, the proof could not proceed.)

By the pumping lemma, can be split into three substrings , where:

,
,
for all .

Here, consists of only 's. Assume . Then .

Now, consider the string (i.e., for ):

Its length is .

However, is not a prime number, because is a prime number, and (where ) is an integer greater than 1.

Thus, , which contradicts the pumping lemma. Therefore, is not regular.

.

Answer: Not regular.

Proof (Sketch):

We can express as:

Here, , and are regular languages.
Regular languages are closed under set union and complement.

If were regular, then would also be regular (by closure properties of regular languages).
However, this contradicts the result from , where was proven to be not regular.
Thus, is not regular.

.

Answer: Regular. In fact, .

Proof:

Consider :

Case 0: If , then .
Case 1: If is a prime, then .
Case 2: If is composite, then , where each is a prime and is a positive integer constant.
- Next, for all .
- Thus, .

Thus, .

Answer: Regular.

.
is regular.

Answer: Not regular.

Proof (Sketch):

Consider the string .
Then, .

Pumping Lemma for Context-Free Language

Lemma (Pumping Lemma for Context-Free Language)

If is a context-free language, then there is a positive constant (pumping length) such that every string of length at least can be written as satisfying the following conditions:

For each ,
, and

Assume L is context-free. Let , which is a string in L.
By the pumping lemma, Then, we have two cases.

Case 1

vxy before the #

has more symbols before # then after.

Case 2

vxy before the #

more 1's but less 0's