Q. The language L = { 0^i 2 1 ^i i>-0 } over the alphabet (0,1,2) is
β
Correct Answer: (B)
is recursive and deterministic CFL
Theory of Computation and Compiler Design MCQs | Page - 2
Dear candidates you will find MCQ questions of Theory of Computation and Compiler Design 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. 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. If s is a string over (0 + 1)* then let n0 (s) denote the number of 0’s in s and n1 (s)the number of l’s in s. Which one of the following languages is not regular?
β
Correct Answer: (C)
L={s € (0+1)* | n0(s) - n1(s) | <= 4}
Q. For S € (0+1)* let d(s)denote the decimal value of s(e.g.d(101)= 5).Let L = {s € (0 + 1) | d (s) mod 5 = 2 and d (s) mod 7 != 4)}Which one of the following statements is true?
β
Correct Answer: (D)
L is regular
Q. Consider the following statements about the context free grammarG = {S - >SS, S - >ab, S - >ba, S - ε}I. G is ambiguousII. G produces all strings with equal number of a’s and b’sIII. G can be accepted by a deterministic PDA.Which combination below expresses all the true statements about G?
β
Correct Answer: (D)
1,2 and 3
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?
β
Correct Answer: (B)
L3 n L1 is recursive
Q. Consider the regular language L =(111+11111)*. The minimum number of states
β
Correct Answer: (D)
9
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?
β
Correct Answer: (B)
L2 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?
β
Correct Answer: (A)
L1 n L2 is a context-free 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?
β
Correct Answer: (B)
L1' is recursive and L2' is not recursively enumerable
Jump to