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:
language accepted by a Turing Machine
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
View Answer Report Discuss Too Difficult! Search Google
Answer: (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
View Answer Report Discuss Too Difficult! Search Google
Answer: (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
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).Both L and L' are r.e. but not 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
View Answer Report Discuss Too Difficult! Search Google
Answer: (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
View Answer Report Discuss Too Difficult! Search Google
Answer: (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 L1
L2' --> 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
View Answer Report Discuss Too Difficult! Search Google
Answer: (b).L1' is recursive and L2' is not recursively enumerable

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
View Answer Report Discuss Too Difficult! Search Google
Answer: (a).M does not halt on any string in (0 + 1)+

118. For any two languages L1 and L2 such that L1 is context free and L2 is recursively enumerable but not recursive, which of the following is/are necessarily true?

1. L1' (complement of L1) is recursive
2. L2' (complement of L2) is recursive
3. L1' is context-free
4. L1' ∪ L2 is recursively enumerable
a. 1 only
b. 3 only
c. 3 and 4 only
d. 1 and 4 only
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).1 and 4 only

119. Let X be a recursive language and Y be a recursively enumerable but not recursive language. Let W and Z be two languages such that Y' reduces to W, and Z reduces to X' (reduction means the standard many-one reduction).
Which one of the following statements is TRUE ?
a. W can be recursively enumerable and Z is recursive
b. W an be recursive and Z is recursively enumerable
c. W is not recursively enumerable and Z is recursive
d. W is not recursively enumerable and Z is not recursive
View Answer Report Discuss Too Difficult! Search Google
Answer: (c).W is not recursively enumerable and Z is recursive

120. Consider the following types of languages:

L1 Regular,
L2: Context-free,
L3: Recursive,
L4: Recursively enumerable.

Which of the following is/are TRUE?

I. L3' U L4 is recursively enumerable
II. L2 U L3 is recursive
III. L1* U L2 is context-free
IV. L1 U L2' is context-free
a. I only
b. I and III only
c. I and IV only
d. I, II and III only
View Answer Report Discuss Too Difficult! Search Google
Answer: (d).I, II and III only