Test: Pumping Lemma - Computer Science Engineering (CSE) MCQ

Pigeon hole principle states the following example: If there exists n=10 pigeons in m=9 holes, then since 10>9, the pigeonhole principle says that at least one hole has more than one pigeon.

The FSA accepts the string pqrs. In terms of pumping lemma, the string pqrs is broken into an x portion an a, a y portion qr and a z portion s.

Finite languages trivially satisfy the pumping lemma by having n equal to the maximum string length in l plus 1.

The process of repeatation is called pumping and so, pumping is the process we perform before we check whether the pumped string belongs to L or not.

We select a string w such that w=xyz and |y|>0 and other conditions. However, there exists an integer n such that |w|>=n for any wÎL.

Given: w =xyz. Here, xyz individually represents strings or rather substrings which we compute over conditions to check the regularity of the language.

Suppose L is a regular language . Then there is an integer n so that for any x∈L and |x|>=n, there are strings u,v,w so that
x= uvw
|uv|<=n
|v|>0
for any m>=0, uv^mw ∈L.

It is the first conditional statement of the lemma that states that |xy|<=n, i.e. the maximum length of the substring xy in w can be n only.

The lemma says, the portion y in xyz cannot be zero or empty i.e. |y|>0, this condition needs to be fulfilled to check the conclusion condition.

Pumping lemma defines an essential property for every regular language in automata theory. It has certain rules which decide whether a language is regular or not.