Automata Theory Multiple Choice Questions 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
Answer: a
Clarification: We use the method of proof by contradiction in pumping lemma to prove that a language is regular or not.
2. The language of balanced paranthesis is
a) regular
b) non regular
c) may be regular
d) none of the mentioned
Answer: b
Clarification: 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
Answer: a
Clarification: 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.
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
Answer: d
Clarification: 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) both (a) and (b)
d) none of the mentioned
Answer: c
Clarification: Collisions are inevitable in a hash table because the number of possible keys exceeds the number of indices in the array.
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
Answer: c
Clarification: 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
Answer: c
Clarification: Y Aharonov proved mathematically the violation of pigeon hole principle in Quantum mechanics and proposed inferometric experiments to test it.
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
Answer: d
Clarification: 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) Both (a) and (b)
d) None of the mentioned
Answer: c
Clarification: 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.
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
Answer: d
Clarification: Pigeon hole principle or Dirichlet’s drawer principle or Dirichlet’s box principle is an example of counting argument whose field is called Combinatorics.