MCQ IN COMPUTER SCIENCE & ENGINEERING

Detailed explanation-1: -Pigeon-hole principle: If there are total p pigeons seating into q holes then what pigeon-hole principle says that at least one hole must have more than one pigeon. Pumping lemma: There is an infinite number of input sequences possible and for every finite automaton there is a finite number of states.

Detailed explanation-2: -For example, given that the population of London is greater than the maximum number of hairs that can be present on a human’s head, then the pigeonhole principle requires that there must be at least two people in London who have the same number of hairs on their heads.

Detailed explanation-3: -In the theory of formal languages, the pumping lemma may refer to: Pumping lemma for regular languages, the fact that all sufficiently long strings in such a language have a substring that can be repeated arbitrarily many times, usually used to prove that certain languages are not regular.

Detailed explanation-4: -Pumping lemma is to be applied to show that certain languages are not regular. It should never be used to show a language is regular. If L is regular, it satisfies the Pumping lemma. If L does not satisfy the Pumping Lemma, it is not regular.

Detailed explanation-5: -Pigeonhole principle states that if n items are put into m containers, with n > m, then at least one container must contain more than one item.