Automata Theory Questions and Answers – Applications of Pumping Lemma/Pigeonhole principle

«
»

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Applications of Pumping Lemma/Pigeonhole principle”.

1. Which kind of proof is used to prove the regularity of a language?
a) Proof by contradiction
b) Direct proof
c) Proof by induction
d) None of the mentioned
View Answer

Answer: a
Explanation: We use the method of proof by contradiction in pumping lemma to prove that a language is regular or not.
advertisement

2. The language of balanced paranthesis is
a) regular
b) non regular
c) may be regular
d) none of the mentioned
View Answer

Answer: b
Explanation: Given n, there is a string of balanced parentheses that begins with more than p left parentheses, so that y will contain entirely of left parentheses. By repeating y, we can produce a string that does not contain the same number of left and right parentheses, and so they cannot be balanced.

3. State true or false:
Statement: Pumping lemma gives a necessary but not sufficient condition for a language to be regular.
a) true
b) false
View Answer

Answer: a
Explanation: The converse of the lemma is not true. There may exists some language which satisfy all the conditions of the lemma and still be non-regular.
Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

4. Which of the following is/are an example of pigeon hole principle?
a) Softball team
b) Sock picking
c) Hair counting
d) All of the mentioned
View Answer

Answer: d
Explanation: There are several applications of pigeonhole principle:
Example: The softball team: Suppose 7 people who want to play softball(n=7 items), with a limitation of only 4 softball teams to choose from. The pigeonhole principle tells us that they cannot all play for different teams; there must be atleast one team featuring atleast two of the seven players.

5. Pigeonhole principle can be applied in the following computer science algorithms:
a) hashing algorithm
b) lossless compression algorithm
c) hashing algorithm and lossless compression algorithm
d) none of the mentioned
View Answer

Answer: c
Explanation: Collisions are inevitable in a hash table because the number of possible keys exceeds the number of indices in the array.
advertisement

6. If n objects are distributed over m places, and n < m, then some of the places receive:
a) at least 2 objects
b) at most 2 objects
c) no object
d) none of the mentioned
View Answer

Answer: c
Explanation: This is one of the alternative formulations of the pigeon hole principle. As n < m, there will exist some place which will not receive any of the object.

7. Which of the following fields may have pigeonhole principle violated?
a) Discrete mathematics
b) Computer Science
c) Quantum Mechanics
d) None of the mentioned
View Answer

Answer: c
Explanation: Y Aharonov proved mathematically the violation of pigeon hole principle in Quantum mechanics and proposed inferometric experiments to test it.
advertisement

8. Which of the following is not an application of Pumping Lemma?
a) {0i1i|i>=0}
b) {0ix|i>=0, x∈{0, 1}* and |x|<=i}
c) {0n| n is prime}
d) None of the mentioned
View Answer

Answer: d
Explanation: None of the mentioned are regular language and are an application to the technique Pumping Lemma. Each one of the mentioned can be proved non regular using the steps in Pumping lemma.

9. Which of the following can refer a language to be non regular?
a) Pumping Lemma
b) Myphill Nerode
c) Pumping Lemma and Myphill Nerode
d) None of the mentioned
View Answer

Answer: c
Explanation: On the contrary, the typical way to prove that a language is to construct either a finite state machine or a regular expression for the language.
advertisement

10. Which of the following is not an example of counting argument?
a) Pigeonhole principle
b) Dirichlet’s drawer principle
c) Dirichlet’s box principle
d) None of the mentioned
View Answer

Answer: d
Explanation: Pigeon hole principle or Dirichlet’s drawer principle or Dirichlet’s box principle is an example of counting argument whose field is called Combinatorics.

Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.