Top 80+ Solved Theory of Computation and Compiler Design MCQ Questions Answer
Q. Let L={w \in (0 + 1)*|w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expression below represents L?
a. (0*10*1)*
b. 0*(10*10*)*
c. 0*(10*1*)*0*
d. 0*1(10*1)*10*
Q. Consider the languages L1={0^{i}1^{j}|i != j}, L2={0^{i}1^{j}|i = j}, L3 = {0^{i}1^{j}|i = 2j+1}, L4 = {0^{i}1^{j}|i != 2j}. Which one of the following statements is true?
a. Only L2 is context free
b. Only L2 and L3 are context free
c. Only L1 and L2 are context free
d. All are context free
Q. Let L = L1 \cap L2, where L1 and L2 are languages as defined below: L1 = {a^{m}b^{m}ca^{n}b^{n} | m, n >= 0 } L2 = {a^{i}b^{j}c^{k} | i, j, k >= 0 } Then L is
a. Not recursive
b. Regular
c. Context free but not regular
d. Recursively enumerable but not context free.
Q. Consider the language L1,L2,L3 as given below. L1={0^{p}1^{q} | p,q \in N}L2={0^{p}1^{q} | p,q \in N and p=q} L3={0^{p}1^{q}1^{r} | p,q,r \in N and p=q=r}Which of the following statements is NOT TRUE?
a. Push Down Automata (PDA) can be used to recognize L1 and L2
b. L1 is a regular language
c. All the three languages are context free
d. Turing machine can be used to recognize all the three languages
Q. Which of the following problems are decidable?1) Does a given program ever produce an output?2) If L is a context-free language, then is L’ (complement of L) also context-free?3) If L is a regular language, then is L’ also regular?4) If L is a recursive language, then, is L’ also recursive?
a. 1, 2, 3, 4
b. 1, 2
c. 2, 3, 4
d. 3, 4
Q. Consider the following Finite State AutomatonThe language accepted by this automaton is given by the regular expression
a. b*ab*ab*ab
b. (a+b)*
c. b*a(a+b)*
d. b*ab*ab
Q. Which of the following languages is regular?
a. {WW^R | W € {0,1}+ }
b. {WW^R X | X W € {0,1}+ }
c. {WW^R | X W € {0,1}+ }
d. {XWW^R | X W € {0,1}+ }
Q. The language L = { 0^i 2 1 ^i i>-0 } over the alphabet (0,1,2) is
a. not recurcise
b. is recursive and deterministic CFL
c. is a regular language
d. is not a deterministic CFL but a CFL
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. 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?
a. L = {s € (0 + 1)*n0 (s) is a 3-digit prime
b. L = {s € (0 + 1)* | for every prefix s’ of s, l 0 (s’) — n1 (s’) | <= 2 }
c. L={s € (0+1)* | n0(s) - n1(s) | <= 4}
d. L = {s € (0 + 1) | n0 (s) mod 7 = n1 (s) mod 5 = 0 }
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?
a. L is recursively enumerable, but not recursive
b. L is recursive, but not context-free
c. L is context-free, but not regular
d. L is regular