PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
pumping lemma (regular languages) (Theorem)

Let $ L$ be a regular language (a.k.a. type 3 language). 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. The length of the subword $ B$ is less than $ n$.
  2. The subword $ B$ cannot be empty (although one of $ A$ or $ C$ might happen to be empty).
  3. For all integers $ k > 0$, it is the case that $ AB^kC$ belongs to $ L$, where exponentiation denotes repetition of a subword $ k$ times.

An important use of this lemma is to show that a language is not regular. (Remember, just because a language happens to be described in terms of an irregular grammar 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 contradiction via this lemma.

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

$\displaystyle L = \{0^p 1^q 0^p \mid p,q > 0 \}.$
Let $ n$ be the number whose existence is guaranteed by the lemma. Now, consider the word $ W = 0^{n+1} 1^{n+1} 0^{n+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. $ A = 0^u, B = 0^v, C = 0^{n+1-u-v} 1^{n+1} 0^{n+1}$
  2. $ A = 0^{n+1-u}, B = 0^u 1^v, C = 1^{n+1-v} 0^{n+1}$
  3. $ A = 0^{n+1} 1^v, B = 1^u, C = 1^{n+1-u-v} 0^{n+1}$
  4. $ A = 0^{n+1} 1^{n+1-v}, B = 1^v 0^u, C = 0^{n+1-u}$
  5. $ A = 0^{n+1} 1^{n+1} 0^u, B = 0^v, C = 0^{n+1-u-v}$
In these cases, $ AB^2C$ would have the following form:
  1. $ AB^2C = 0^{n+1+v} 1^{n+1} 0^{n+1}$
  2. $ AB^2C = 0^{n+1} 1^v 0^u 1^{n+1} 0^{n+1}$
  3. $ AB^2C = 0^{n+1} 1^{n+1+u} 0^{n+1}$
  4. $ AB^2C = 0^{n+1} 1^{n+1} 0^u 1^v 0^{n+1}$
  5. $ AB^2C = 0^{n+1} 1^{n+1} 0^{n+1+u}$

It is easy to see that, in each of these five cases, $ AB^2C \notin L$. Hence $ L$ cannot be a regular language.



"pumping lemma (regular languages)" is owned by rspuzio.
(view preamble)

View style:

See Also: pumping lemma (context-free languages)

Other names:  pumping lemma

Cross-references: easy to see, contradiction, terms, regular, word, length, integer, language, type, regular language

This is version 5 of pumping lemma (regular languages), born on 2006-10-28, modified 2006-12-25.
Object id is 8489, canonical name is PumpingLemmaRegularLanguages.
Accessed 426 times total.

Classification:
AMS MSC68Q42 (Computer science :: Theory of computing :: Grammars and rewriting systems)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
rate | post | correct | update request | prove | add result | add corollary | add example | add (any)