Top 150+ Solved Theory of Computation MCQ Questions Answer
Q. A language is regular if and only if
a. Accepted by DFA
b. Accepted by PDA
c. Accepted by LBA
d. Accepted by Turing machine
Q. Which of the following is not a regular expression?
a. [(a+b)*-(aa+bb)]*
b. [(0+1)-(0b+a1)*(a+b)]*
c. (01+11+10)*
d. (1+2+0)*(1+2)*
Q. Which of the following is TRUE?
a. Every subset of a regular set is regular
b. Every finite subset of a non-regular set is regular
c. The union of two non-regular sets is not regular
d. Infinite union of finite sets is regular
Q. Which one of the following languages over the alphabet {0,1} is describedby the regular 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 statement is true for a regular language L over {a} whose minimal finite state automation has two states?
a. L must be either {an I n is odd} or {an I n is even}
b. L must be {an I n is odd}
c. L must be {an I n is even}
d. L must be {an I n = 0}
Q. The …………. is said to be ambiguous if there exist at least one word of its language that can be generated by the different production tree .
a. CFL
b. CFG
c. GTG
d. None of the given
Q. Which of the following problems is undecidable?
a. Membership problem for CFGs
b. Ambiguity problem for CFGs
c. Finiteness problem for Finite state automata FSAs
d. Equivalence problem for FSAs