1.4 NONREGULAR LANGUAGES

Question 1

Our technique for proving nonregularity stems from a theorem about regular languages, traditionally called the pumping lemma.

Answer 1

This theorem states that all regular languages have a special property. If we can show that a language does not have this property, we are guaranteed that it is not regular.

The property states that all strings in the language can be “pumped” if they are at least as long as a certain special value, called the pumping length.

Question 2

Pumping lemma

Answer 2

If A is a regular language, then there is a number p (the pumping length) where if s is any string in A of length at least p, then s may be divided into three pieces, s = xyz, satisfying the following conditions:

1. for each i ≥ 0, xyiz ∈ A,
2. |y| > 0, and
3. |xy| ≤ p.

Question 3

How to use the pumping lemma?

Answer 3

To use the pumping lemma to prove that a language B is not regular, first assume that B is regular in order to obtain a contradiction.

Then use the pumping lemma to guarantee the existence of a pumping length p such that all strings of length p or greater in B can be pumped.

Next, find a string s in B that has length p or greater but that cannot be pumped.

Finally, demonstrate that s cannot be pumped by considering all ways of dividing s into x, y, and z (taking condition 3 of the pumping lemma into account if convenient) and, for each such division, finding a value i where xyiz ̸∈ B.