Pumping Lemma

  • Post author:
Download PDF
Advertisement

Pumping Lemma (PL)

Without any proof the string or language is accepted as true, this process is known as Pumping lemma.

Pumping Theorem

Let ‘L’ be a regular language. There exist an integer P≥1 such that every string ‘w’ in ‘L’ of length at least ‘P’.

It can be written as w = xyz satisfying the following conditions.

Satisfaction:

ǀ y ǀ ≥ 1                        xy ≤ P

xykz is also in L         for all I ≥ 0

Example:

The pumping lemma (PL) for ‘a (bc) d’ has the following example:

  • a = x
  • (bc) = y
  • d = z

The finite automata of this pumping lemma (PL) can be drawn as:

pumping lemma

Applications for Pumping Lemma (PL)

PL can be applied for the confirmation of the following languages are not regular. It should never be used to show a language is regular.

Advertisement

  • If L is a regular language, it satisfies the PL.
  • If L does not satisfy PL, it is non-regular.
Method to prove that a language L is not regular.
  • First of all, we have to assume that Lis regular language.
  • So, the PL should hold for L.
  • Use the PL to obtain a contradiction −.
    • Select w such that |w| ≥ c.
    • Select y such that |y| ≥ 1.
    • Select x such that |xy| ≤ c.
    • Assign the remaining string to.
    • Select k such that the resulting string is not in L.

FA to RE expression construction

Advertisement