A directory of Objective Type Questions covering all the Computer Science subjects. Here you can access and discuss Multiple choice questions and answers for various compitative exams and interviews.

 111. Which of the following is true for the language given below: a. It is not accepted by a Turing Machine b. It is regular but not context-free c. It is context-free but not regular d. It is neither regular nor context-free, but accepted by a Turing machine

 112. If L and L' are recursively enumerable, then L is a. regular b. context-free c. context-sensitive d. recursive

 113. Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility? a. Neither L nor L' is recursively enumerable (r.e.) b. One of L and L' is r.e. but not recursive; the other is not r.e c. Both L and L' are r.e. but not recursive d. Both L and L' are recursive

 114. Let A ≤m B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE? a. If A ≤m B and B is recursive then A is recursive b. If A ≤m B and A is undecidable then B is undecidable c. If A ≤m B and B is recursively enumerable then A is recursively enumerable d. If A ≤m B and B is not recursively enumerable then A is not recursively enumerable

 115. 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)mod5 = 2 and d(s)mod7 != 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

 116. 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?L1' --> Complement of L1L2' --> Complement of L2 a. L1' is recursive and L2' is recursively enumer­able b. L1' is recursive and L2' is not recursively enumerable c. L1' and L2' are recursively enumerable d. L1' is recursively enumerable and L2' is recursive

 117. A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table  0 1 B q0  q1, 1, R q1, 1, R  Halt q1  q1, 1, R   q0, 1, L   q0, B, L   The table is interpreted as illustrated below. The entry (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q1. Which of the following statements is true about M ? a. M does not halt on any string in (0 + 1)+ b. M does not halt on any string in (00 + 1)* c. M halts on all string ending in a 0 d. M halts on all string ending in a 1