Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

Theory of Computation MCQ (Multiple Choice Questions)

 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

Previous Post Next Post

Responsive Ad