UGC NET CSE | November 2017 | Part 3 | Question: 19

Question

The logic of pumping lemma is an example of _________

• A. Iteration
• B. Recursion
• C. The divide and conquer principle
• D. The pigeon – hole principle

Answer 1

Pigeon-hole principle states that if there are n pigeons fly into m hole and n > m then atleast one hole must contain more than one pigeons. And logic of pumping lemma states that- finite state automaton can assume only a finite number of states and because there are infintely many input sequence, by the pigeon hole principle , there must be atleast one state to which the automata returns over and over again.

So, option (D) is correct. 

Comments

Consider a DFA which accepts empty set. Now, all the infinite input sequences go to dead state. Is this an example of pumping lemma?

Instead of state and input sequences, you must say paths and strings in the language.