1,375 views
2 votes
2 votes
The proof of pumping lemma is an example of :-

(A) iteration

(B) recursion

(C) pigeonhole principle

(D) None of These

1 Answer

Best answer
2 votes
2 votes

The infomal pumping lemma principle can be stated as: (for regularity checking similarly can be reduced to CFL as well) If there is a state in Automaton which is self loop and machine pumped it once only to accept the string in the language yet pumped twice will produce a string which is not in language therefore its not regular .Formal definition can be studied from here .

Now,There is always a finite state is a finite automaton and if a infinite language is generated therefore it implies that there is no one to one association b/w the sets. and therefore it implies that there must be two element in the codomain which have same image which can be pumped again .


Similar to statment of PIGENHOLE. which states the if a set has $N$ elements and other set has $M$ elements and there is one to one mapping but $N>M$ which implies one to one mapping is not at all possible.
 

Footer Note : No such statments can be made for recursion and iterative method therefore can be eliminated.

selected by

Related questions

0 votes
0 votes
0 answers
1
jg662 asked Feb 22
80 views
Use the Pumping Lemma to show that the following languages over Σ={�,�}Σ={a,b} are not regular. In each case, carefully describe the string that will be pumped and ...
0 votes
0 votes
1 answer
3
shallowfalcon asked Oct 17, 2022
434 views
If L = { x == y | where x and y are equal binary numbers} and Σ = {0, 1, =}How can I prove that L is not a regular language using pumping lemma and contradiction?
0 votes
0 votes
1 answer
4
srestha asked Apr 19, 2019
669 views
How by Pumping Lemma we can prove that“context free grammar generate an infinite number of strings”and here what could be pumping length ?