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

  1. Pingback: ugg france pas cher
  2. Pingback: bottes filles chipie

Leave a Reply