October 26, 2023
October 26, 2023
October 26, 2023
###### JNU 2018-1 PhD CS
October 26, 2023
 Question 4
The basic logic of pumping lemma can be considered as a good example of
 A recursion B iteration C pigeonhole principle D divide-and-conquer
Question 4 Explanation:
The pigeonhole principle states that if you have fewer holes than objects then at least one holes has multiple objects in it.It states that put one object in each hole and then there must exist at least one hole which must have more than one object.
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. Hence, the logic of pumping lemma is a good example of the pigeonhole principle.
Question 4 Explanation:
The pigeonhole principle states that if you have fewer holes than objects then at least one holes has multiple objects in it.It states that put one object in each hole and then there must exist at least one hole which must have more than one object.
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. Hence, the logic of pumping lemma is a good example of the pigeonhole principle.