Top 80+ Solved Theory of Computation and Compiler Design MCQ Questions Answer
Q. Which of the following statements in true?
a. If a language is context free it can always be accepted by a deterministic push-down automaton
b. The union of two context free languages is context free
c. The intersection of two context free languages is context free
d. The complement of a context free language is context free
Q. Which of the following is true for the language {a^p} p is prine ?
a. It is not accepted by a turing machine
b. It is regular but not context free
c. It is context free but not regular
d. It is neither regular nor context free but accepted by a turing machine
Q. Which of the following are decidable ?1. whether the intersection of two regular language is infinite.2. whether a give context free language is regular3. whether two push down automata accept the same language.4. whether a given grammar is context free
a. 1 and 2
b. 1 and 4
c. 2 and 3
d. 2 and 4
Q. If L and L' are recursively enumerable, then L is
a. regular
b. context free
c. context sensitive
d. recursive
Q. Consider the CFG with {S,A,B) as the non-terminal alphabet, {a,b) as the terminal alphabet, S as the start symbol and the following set of production rulesS --> aB S --> bAB --> b A --> aB --> bS A --> aSB --> aBB A --> bAAWhich of the following strings is generated by the grammar?
a. aaaabb
b. aabbbb
c. aabbab
d. abbbba
Q. Consider the following context free languages:L1 = {0^i 1^j 2^k | i+j = k}L2 = {0^i 1^j 2^k | i = j or j = k}L3 = {0^i 1^j | i = 2j+1}Which of the following option is true?
a. L1, L2 and L3 can be recognized by Deterministic Push down automata
b. L1, L2 can be recognized by Deterministic Push down automata
c. L1, L3 can be recognized by Deterministic Push down automata
d. None of the above
Q. Which of the following are decidable?I. Whether the intersection of two regular languages is infiniteII. Whether a given context-free language is regularIII. Whether two push-down automata accept the same languageIV. Whether a given grammar is context-free
a. I and II
b. I and IV
c. II and III
d. II and IV
Q. Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. Which one of the following is TRUE?
a. P3 is decidable if P1 is reducible to P3
b. P3 is undecidable if P3 is reducible to P2
c. P3 is undecidable if P2 is reducible to P3
d. P3 is decidable if P3 is reducible to P2's complement
Q. Consider the following decision problems:(P1) Does a given finite state machine accept a given string(P2) Does a given context free grammar generate an infinite number of stingsWhich of the following statements is true?
a. Both (P1) and (P2) are decidable
b. Neither (P1) nor (P2) are decidable
c. Only (P1) is decidable
d. Only (P2) is decidable
Q. Consider the following identities for regular expressions: (a) (r + s)* = (s + r)* (b) (r*)* = r* (c) (r* s*)* = (r + s)* Which of the above identities are true?
a. (a) and (b) only
b. (b) and (c) only
c. (c) and (a) only
d. (a), (b) and (c)
Q. In a compiler, keywords of a language are recognized during
a. parsing of the program
b. the code generation
c. the lexical analysis of the program
d. dataflow analysis