1. 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
Ans- d. All of the mentioned
2. The language of balanced paranthesis is:
a. regular
b. non regular
c. may be regular
d. none of the mentioned
Ans- b. non regular
3. 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
Ans- a. Proof by contradiction
4. Which of the following one can relate to the given statement: Statement: If n items are put into m containers, with n>m, then atleast one container must contain more than one item.
a. Pumping lemma
b. Pigeon Hole principle
c. Count principle
d. None of the mentioned
Ans- b. Pigeon Hole principle
5. Let w be a string and fragmented by three variable x, y, and z as per pumping lemma. What does these variables represent?
a. string count
b. string
c. Both (a) and (b)
d. None of the mentioned
Ans- a. string count
6. Fill in the blank in terms of p, where p is the maximum string length in L. Statement: Finite languages trivially satisfy the pumping lemma by having n = __
a. p*1
b. p+1
c. p-1
d. None of the mentioned
Ans- b. p+1
7. There exists a language L. We define a string w such that w?L and w=xyz and |w| >=n for some constant integer n.What can be the maximum length of the substring xy i.e. |xy|<=?
a. n
b. |y|
c. |x|
d. None of the mentioned
Ans- a. n
8. Let w= xyz and y refers to the middle portion and |y|>0.What do we call the process of repeating y 0 or more times before checking that they still belong to the language L or not?
a. Generating
b. Pumping
c. Producing
d. None of the mentioned
Ans- b. Pumping
9. While applying Pumping lemma over a language, we consider a string w that belong to L and fragment it into ___ parts.
a. 2
b. 5
c. 3
d. 6
Ans- c. 3
10. Relate the following statement: All sufficiently long words in a regular language can have a middle section of words repeated a number of times to produce a new word which also lies within the same language.
a. Turing Machine
b. Pumping Lemma
c. Arden's theorem
d. None of the mentioned
Ans- b. Pumping Lemma