Q. Let L denotes the language generated by the grammar S – OSO/00. Which of the following is true?
✅ Correct Answer: (B)
L is regular but not O
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. 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?
✅ Correct Answer: (C)
S=T
Q. Which of the following pairs have DIFFERENT expressive power?
✅ Correct Answer: (B)
Deterministic push down automata (DPDA) and Non-deterministic pushdown automata
Q. 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
✅ Correct Answer: (B)
P-3, Q-1, R-4, S-2
Q. 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
✅ Correct Answer: (A)
15 states
Q. Any Language generated by an unrestricted grammar is:
✅ Correct Answer: (A)
Recursive
Q. The Family of recursive language is not closed under which of the following operations:
✅ Correct Answer: (D)
None of the above.
Q. If PCP is decidable then MPCP is
✅ Correct Answer: (C)
Can’t Say
Q. 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?
✅ Correct Answer: (A)
Both DHAM3 and SHAM3 are NP-hard
Jump to