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:
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.