pumping lemma (regular languages)


Lemma 1.

Let L be a regular language (a.k.a. type 3 languagePlanetmathPlanetmath). Then there exist an integer n such that, if the length of a word W is greater than n, then W=ABC where A,B,C are subwords such that

  1. 1.

    The length of the subword B is less than n.

  2. 2.

    The subword B cannot be empty (although one of A or C might happen to be empty).

  3. 3.

    For all integers k>0, it is the case that ABkC belongs to L, where exponentiationPlanetmathPlanetmath denotes repetition of a subword k times.

An important use of this lemma is to show that a language is not regularPlanetmathPlanetmath. (Remember, just because a language happens to be described in terms of an irregular grammarMathworldPlanetmath does not automatically preclude the possibility of describing the same language also by a regular grammar.) The idea is to assume that the language is regular, then arrive at a contradictionMathworldPlanetmathPlanetmath via this lemma.

An example of such a use of this lemma is afforded by the language

L={0p1q0pp,q>0}.

Let n be the number whose existence is guaranteed by the lemma. Now, consider the word W=0n+11n+10n+1. There must exist subwords A,B,C such that W=ABC and B must be of length less than n. The only possibilities are the following

  1. 1.

    A=0u,B=0v,C=0n+1-u-v1n+10n+1

  2. 2.

    A=0n+1-u,B=0u1v,C=1n+1-v0n+1

  3. 3.

    A=0n+11v,B=1u,C=1n+1-u-v0n+1

  4. 4.

    A=0n+11n+1-v,B=1v0u,C=0n+1-u

  5. 5.

    A=0n+11n+10u,B=0v,C=0n+1-u-v

In these cases, AB2C would have the following form:

  1. 1.

    AB2C=0n+1+v1n+10n+1

  2. 2.

    AB2C=0n+11v0u1n+10n+1

  3. 3.

    AB2C=0n+11n+1+u0n+1

  4. 4.

    AB2C=0n+11n+10u1v0n+1

  5. 5.

    AB2C=0n+11n+10n+1+u

It is easy to see that, in each of these five cases, AB2CL. Hence L cannot be a regular language.

Title pumping lemmaPlanetmathPlanetmath (regular languages)
Canonical name PumpingLemmaregularLanguages
Date of creation 2013-03-22 16:21:17
Last modified on 2013-03-22 16:21:17
Owner rspuzio (6075)
Last modified by rspuzio (6075)
Numerical id 9
Author rspuzio (6075)
Entry type Theorem
Classification msc 68Q42
Synonym pumping lemma
Related topic PumpingLemma