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 contextfree 
c.  It is contextfree but not regular 
d.  It is neither regular nor contextfree, but accepted by a Turing machine 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).It is neither regular nor contextfree, but accepted by a Turing machine

112.  If L and L' are recursively enumerable, then L is 
a.  regular 
b.  contextfree 
c.  contextsensitive 
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 manytoone 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 contextfree 
c.  L is contextfree, 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 enumerable 
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 contextfree 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 manyone 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: Contextfree, 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 contextfree IV. L1 U L2' is contextfree 
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
