Pumping Lemma

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

Zitoc

We are a team of writers, researchers, and editors who are passionate about helping others live their best lives. We believe that life is a beautiful gift. We try to live our lives to the fullest and enjoy every moment. We are always learning and growing, and we cherish the relationships we have with our family and friends.