Home / Engineering / Theory of Computation MCQs / Page 6

# Theory of Computation MCQs | Page - 6

Dear candidates you will find MCQ questions of Theory of Computation here. Learn these questions and prepare yourself for coming examinations and interviews. You can check the right answer of any question by clicking on any option or by clicking view answer button.

(A) 1 only
(B) 1 and 3
(C) 2 and 3
(D) 1,2 and 3

(A) 3
(B) 5
(C) 8
(D) 9

## `Q. 53) Give a production grammar for the language L = {x/x ∈ (a,b)*, the number of a’s in x is multiple of 3}.`

(A) {S->bS,S->b,S->aA,S->bA,A->aB,B->bB,B->aS,S->a}
(B) {S->aS,S->bA,A->bB,B->bBa,B->bB}
(C) {S->aaS,S->bbA,A->bB,B->ba}
(D) None of the above

## `Q. 54) The production Grammar is {S->aSbb,S->abb} is`

(A) type-3 grammar
(B) type-2 grammar
(C) type-1 grammar
(D) type-0 grammar

## `Q. 55) Regular expression (x/y)(x/y) denotes the set`

(A) {xy,xy}
(B) {xx,xy,yx,yy}
(C) {x,y}
(D) {x,y,xy}

(A) (0+1+2)*
(B) 0*1*2*
(C) 0* + 1 + 2
(D) (0+1)*2*

## `Q. 57) Suppose that a problem A is known to have a polynomial-time verification algorithm. Which of the following statements can be deduced.`

(A) A is in NP.
(B) A is in NP but not P
(C) A is in both NP and P.
(D) A is NP-complete.

## `Q. 58) Which of the following assertions about Turing Machines is true? Blank symbol(s) may occur in the input. At any stage of a computation, there are only finitely many non-blank Symbols on the tape.`

(A) Assertions (a) and (b) are both true.
(B) Neither (a) nor (b) is true.
(C) Both False
(D) None of above

## `Q. 59) A PC not connected to a network is equivalent to`

(A) A Deterministic Finite-State Automaton,
(B) A Turing Machine,
(C) A Push-Down Automaton,
(D) None of the above.

## `Q. 60) Recursively enumerable languages are not closed under:`

(A) Union
(B) Intersection
(C) Complementation
(D) Concatenation

Download our easy to use, user friendly Android App from Play Store. And learn MCQs with one click.