Home / Engineering / Theory of Computation MCQs / Page 5

# Theory of Computation MCQs | Page - 5

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.

M

Mr. Dubey • 51.17K Points
Coach

## `Q. 41) Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true?`

(A) L = O
(B) L is regular but not O
(C) L is context free but not regular
(D) L is not context free

M

Mr. Dubey • 51.17K Points
Coach

## `Q. 42) Let S and T be language over ={a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?`

(A) ScT (S is a subset of T)
(B) TcS (T is a subset of S)
(C) S=T
(D) SnT=Ø

M

Mr. Dubey • 51.17K Points
Coach

## `Q. 43) Which of the following pairs have DIFFERENT expressive power?`

(A) Deterministic finite automata (DFA) and Non-Deterministic finite automata(NFA)
(B) Deterministic push down automata (DPDA) and Non-deterministic pushdown automata
(C) Deterministic single-tape Turing machine and Non-deterministic single-tape Turing Machine
(D) Single-tape Turing machine and multi-tape Turing machine

M

Mr. Dubey • 51.17K Points
Coach

## `Q. 44) Match all items in Group 1 with correct options from those given in Group 2. List I List II**spaceP. Regular Expression 1. Syntax analysis**spaceQ. Push down automata 2. Code Generation**spaceR. Dataflow analysis 3. Lexical analysis**spaceS. Register allocation 4. Code optimization`

(A) P-4, Q-1, R-2, S-3
(B) P-3, Q-1, R-4, S-2
(C) P-3, Q-4, R-1, S-2
(D) P-2, Q-1, R-4, S-3

M

Mr. Dubey • 51.17K Points
Coach

## `Q. 45) A minimum state deterministic finite automation accepting the language L = {W W € {0,1}* , number of 0's and 1's in W are divisible by 3 and 5 respectively has`

(A) 15 states
(B) 11 states
(C) 10 states
(D) 9 states

M

Mr. Dubey • 51.17K Points
Coach

## `Q. 46) Any Language generated by an unrestricted grammar is:`

(A) Recursive
(B) Recursively Enumerable
(C) Not Recursive
(D) None of the above

M

Mr. Dubey • 51.17K Points
Coach

## `Q. 47) The Family of recursive language is not closed under which of the following operations:`

(A) Union
(B) Intersection
(C) Complementation
(D) None of the above.

M

Mr. Dubey • 51.17K Points
Coach

## `Q. 48) PCP is:`

(A) Decidable
(B) Undecidable
(C) Sometimes Decidable
(D) None of the

M

Mr. Dubey • 51.17K Points
Coach

## `Q. 49) If PCP is decidable then MPCP is`

(A) Decidable
(B) Undecidable
(C) Can’t Say
(D) None of the

M

Mr. Dubey • 51.17K Points
Coach

## `Q. 50) Let SHAM3 be the problem of finding a Hamiltonian cycle in a graph G =(V,E)with V divisible by 3 and DHAM3 be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?`

(A) Both DHAM3 and SHAM3 are NP-hard
(B) SHAM3 is NP-hard, but DHAM3 is not
(C) DHAM3 is NP-hard, but SHAM3 is not
(D) Neither DHAM3 nor SHAM3 is NP-hard

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