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.

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
View Answer Discuss Share

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=Ø
View Answer Discuss Share

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
View Answer Discuss Share

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
View Answer Discuss Share

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
View Answer Discuss Share

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

(A) Recursive
(B) Recursively Enumerable
(C) Not Recursive
(D) None of the above
View Answer Discuss Share

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.
View Answer Discuss Share

Q. 48) PCP is:

(A) Decidable
(B) Undecidable
(C) Sometimes Decidable
(D) None of the
View Answer Discuss Share

Q. 49) If PCP is decidable then MPCP is

(A) Decidable
(B) Undecidable
(C) Can’t Say
(D) None of the
View Answer Discuss Share

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
View Answer Discuss Share