Top 80+ Solved Theory of Computation and Compiler Design MCQ Questions Answer
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?
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
Q. Let L1 be a regular language, L2 be a deterministic context-free language and L3 a recursively enumerable, but not recursive, language. Which one of the following statements is false?
a. L1 n L2 is a deterministic CFL
b. L3 n L1 is recursive
c. L1 U L2 is context free
d. L1 n L2 n L3 is recursively enumerable
Q. Consider the languages: GATE[2005]L1 = {wwR w €{0, 1} *1L2 ={w#ww € {O,1}*},where # is a special symbolL3 ={www € {0,1}*}Which one of the following is TRUE?
a. L1 is a deterministic CFL
b. L2 is a deterministic CFL
c. L3 is a CFL, but not a deterministic CFL
d. L3 is a deterministic CFL
Q. Consider the languages: L1 ={a^n b^n c^m | n,m >01 and L2 ={a^n b^m c^m |n,m> o) Which one of the following statements is FALSE?
a. L1 n L2 is a context-free language
b. L1 u L2 is a context-free language
c. L1 and L2 are context-free languages
d. L1 n L2 is a context sensitive language
Q. Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?
a. L1' is recursive and L2' is recursively enumerable
b. L1' is recursive and L2' is not recursively enumerable
c. L1' and L2' are recursively enumerable
d. L1' is recursively enumerable and L2' is recursive
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 enumberable
c. L2 intersection L1 is recursively enumberable
d. L2 union L1 is recursively enumberable
Q. S –> aSa| bSb| a| b ;The language generated by the above grammar over the alphabet {a,b} is the set of
a. All palindromes.
b. All odd length palindromes.
c. Strings that begin and end with the same symbol
d. All even length palindromes.
Q. Which one of the following languages over the alphabet {0,1} is described by theregular expression: (0+1)*0(0+1)*0(0+1)*?
a. The set of all strings containing the substring 00.
b. The set of all strings containing at most two 0’s.
c. The set of all strings containing at least two 0’s.
d. The set of all strings that begin and end with either 0 or 1.
Q. Which one of the following is FALSE?
a. There is unique minimal DFA for every regular language
b. Every NFA can be converted to an equivalent PDA.
c. Complement of every context-free language is recursive.
d. Every nondeterministic PDA can be converted to an equivalent deterministic PDA.
Q. Match all items in Group 1 with correct options from those given in Group 2.List I List IIP. Regular Expression 1. Syntax analysisQ. Push down automata 2. Code GenerationR. Dataflow analysis 3. Lexical analysisS. 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. 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. 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. 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
Q. Consider the following two statements:S1: { 0^2n |n >= l} is a regu1ar languageS2: { 0^m 0^n 0^(m+n) l m >= 1 and n >= 2} is a regu1ar languageWhich of the following statements is correct?
a. Only S1 is correct
b. Only S2 is correct
c. Both S1 and S2 are correct
d. None of S1 and S2 is correct