09/21 - Subset Construction Project 2.9

Question 1

Theorem 2.9.1 (Pumping Lemma for Regular Languages)

Answer 1

Let A be a regular language. Then there exists an integer p ≥ 1, called the pumping length, such that the following holds: Every string s in A, with |s| ≥ p, can be written as s = xyz, such that:

1. y /= Ee (i.e.,|y|≥1),
2. |xy| ≤ p, and
3. for all i≥0, xy^iz ∈ A.

In words, the pumping lemma states that by replacing the portion y in s by zero or more copies of it, the resulting string is still in the language A.