NIELIT 2017 OCT Scientific Assistant A (CS) - Section B: 12

Question

The logic of pumping lemma is a good example of

• A. the pigeon-hole principle
• B. the divide and conquer technique
• C. recursion
• D. iteration

Comments

option A. you can follow the link below for detailed answer

Answer 1

Option (A) pigeon – hole principle

https://gateoverflow.in/166395/ugcnet-nov2017-iii-19

Answer 2

A

Explanation: pigeon hole principle states that, if we have n objects & m boxes s.t. #objects > #boxes & we are required to put ever object in a box, then at least 1 box will contain more than 2 objects.

this same principle applies for pumping lemma in a bit different form.

if a string of length n need to be accepted by a FA then it require at least n+1 states. Now if this string have some part repeating then we may have to apply loop on at least 1 state.