Computer science: Theory Of computation MCQs
56. Question
Which of the following pairs have DIFFERENT expressive power?
Answer
57. Question
Definition of a language L with alphabet {a} is given as following
L = {ank |k > 0, and n is a positive integer constant}
What is the minimum number of states needed in a DFA to recognize L?
Answer
58. Question
Consider the languages L1, L2 and L3 as given below
L1 = {0p1q|p,q ∈ N}
L2 = {0p1q|p,q ∈ N and p = q} and
L3 = {0p1q0r|p,q,r ∈ N and p = q = r}
Which of the following statements is NOT TRUE?
Answer
59. Question
Which of the following statements is/are FALSE?
(1) For every non-deterministic Turing machine, there exists an equivalent deterministic Turing machine.
(2) Turing recognizable languages are closed under union and complementation.
(3) Turing decidable languages are closed under intersection and complementation
(4) Turing recognizable languages are closed under union and intersection.
Answer
60. Question
Consider the languages L1 = Φ and L = {a} . Which one of the following represents L1L2*UL1* ?
Answer
4 thoughts on “Computer science: Theory Of computation MCQs”