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

xy^kz 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:

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.

• 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