Global Web Forum

Muhammad

بِسمِ اللَّهِ الرَّحمٰنِ الرَّحيمِ

From: Sahiwal Division

Registered: 2012-03-22

Posts: 22,197

Website

The logic of pumping lemma is a good example of?

Programming Languages Quizzes Theory Of Computation

Question:
The logic of pumping lemma is a good example of

Option A):
recursion
Option B):
divide-and-conquer technique
Option C):
pigeon-hole principle
Option D):
iteration

Correct Answer is Option C):
pigeon-hole principle

Explanation:
The  pigeon hole principle is nothing more than the obvious remark: if you have fewer pigeon holes than pigeons and you put every pigeon in a pigeon hole, then there must result at least one pigeon hole with more than one pigeon. It is surprising how useful this can be as a proof strategy.
In the theory of formal languages in computability theory, a pumping lemma or pumping argument states that, for a particular language to be a member of a language class, any sufficiently long string in the language contains a section, or sections, that can be removed, or repeated any number of times, with the resulting string remaining in that language. The proofs of these lemmas typically require counting arguments such as the pigeonhole principle.

---

Online Web Tutorials And Interview Questions With Answers Forum:
https://globalguideline.com/forum/