Andhra University 2006 B.E Information Technology COMPUTER SCIENCE
Wednesday, 01 May 2013 08:05Web
Page 10 of 15
(a) L one Î P and L two is finite
(b) L one Î NP and L two Î P
(c) L one is undecidable and L two is decidable
(d) L one is recursively enumerable and L two is recursive
53. A single tape Turing Machine M has 2 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 defined in the subsequent 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 beneath.
The entry (q1, 1, R) in row q0 and column one signifies that if M is in state q0 and reads one on the current tape square, then it writes one on the identical tape square, moves its tape head 1 position to the right and transitions to state q1. Which of the subsequent statements is actual 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 one
54. describe languages L 0 and L one as follows:
L 0 = {
L one = {
Here
(a) L is recursively enumerable, but is not
(b) is recursively enumerable, but L is not
(c) Both Land L are recursive
(d) Neither L nor is recursively enumerable
55. Consider the NFA M shown beneath.
Let the language accepted by M be L. Let L one be the language accepted by the NFA M1, found by changing the accepting state of M to a non-accepting state and by changing the non-accepting state of M to accepting states. Which of the subsequent statements is true?
L one = {O, 1}* - L
L one = {O, 1}*
L one Í L
L one = L
56. Consider the grammar shown beneath
S ® i E t S S ' l a
| Earning: Approval pending. |
