Paul Nicholls Stuff

11Dec/080

Pumping Lengths

Pumping Lemma describes a fundamental property of regular languages, in simple terms it states that in order for a language to be regular, sufficiently long words may be pumped, where pumped means that a given section of the middle of the word, can be repeated a number of times to produce a new word which still lies within the same language.

Formally, Let L be a regular language. Then there exists an integer p \leq 1 depending only on L such that every string w in L of length at least p (the "pumping length") can be written as w = xyz (i.e., w can be divided into three substrings), satisfying the following conditions:

  1. |y| > 0
  2. |xy| \leq p
  3. \mbox{for all } i \leq 0, xy^iz \in L

Why Is This Relevant?

This method can be used to show a language is not regular, since if it meets the above criteria then it must be a regular language, so a proof by contradiction can be used to show which languages are not regular and thus not able to be modelled by NFAs or DFAs.

Tagged as: , Leave a comment
Comments (0) Trackbacks (0)

No comments yet.


Leave a comment

(required)

No trackbacks yet.