Top 150+ Solved Theory of Computation MCQ Questions Answer
Q. Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?
a. L2-L1 is recursively enumerable
b. L1-L3 is recursively enumerable
c. L2 intersection L1 is recursively enumerable
d. L2 union L1 is recursively enumerable
Q. Let L denotes the language generated by the grammar S – OSO/00. Which of thefollowing 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
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?
a. ScT (S is a subset of T)
b. TcS (T is a subset of S)
c. S=T
d. SnT=Ø
Q. 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
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
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
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
a. 15 states
b. 11 states
c. 10 states
d. 9 states
Q. Any Language generated by an unrestricted grammar is:
a. Recursive
b. Recursively Enumerable
c. Not Recursive
d. None of the above
Q. The Family of recursive language is not closed under which of the followingoperations:
a. Union
b. Intersection
c. Complementation
d. None of the above.
Q. Consider a language L for which there exists a Turing machine ™, T, that accepts every word in L and either rejects or loops for every word that is not in L. The language L is
a. NP hard
b. NP complete
c. Recursive
d. Recursively enumerable
Q. Consider the following statementsI. Recursive languages are closed under complementationII. Recursively enumerable languages are closed under unionIII. Recursively enumerable languages are closed under complementationWhich of the above statement are TRUE?
a. I only
b. I and II
c. I and III
d. II and III
Q. Recursively enumerable languages are not closed under
a. Union
b. homomorphism
c. complementation
d. concatenation
Q. Which of the following problem is undecidable?
a. Membership problem for CFL
b. Membership problem for regular sets
c. Membership problem for CSL
d. Membership problem for type 0 languages
Q. Recursive languages are
a. A proper superset of CFL
b. Always recognized by PDA
c. Are also called type 0 languages
d. Always recognized by FSA