Q81. Let L be a language accepted by some nondeterministic multitape turing
machine and L1 its complement also accepted by a two pushdown tape machine then
choose the correct statement
a) L is recursively enumerable but not necessarily recursive
b) L is recursive but L1 is not necessarily recursive
c) Both L and L1 are recursively enumerable but not necessarily recrsive
d) Both L and L1 are recursive
Q82. Let L be a language accepted by some nondeterministic multitape turing
machine and L1 its complement also accepted by a nondeterministic two pushdown
tape machine then choose the correct statement
a) L is recursively enumerable but not necessarily recursive
b) L is recursive but L1 is not necessarily recursive
c) Both L and L1 are recursively enumerable but not necessarily recursive
d) Both L and L1 are recursive
Q83. Choose the correct statement
a) there exists a universal turing machine which can simulate any turing machine
M on its input w
b) there does not exist a universal turing machine which can simulate any turing
machine on its input w
c) the set Ld={<Mi,wi>| the encoding Mi of the ith turing machine does not
accept the input wi, in an enumeration of turing machines and input strings} is
recursively enumerable
d) the universal language is recursive
Q84. The printing problem of turing machines is whether a turing machine ever
prints a 1 on its tape. Ram takes the set L={<M,w>| encoding of turing machine M
that does not accept w} which is known to be undecidable. He modifies M such
that in an accepting state no moves are made. Shyam further modifes M to M1 so
that in an accepting state it prints a 1 and then halts. Choose the correct
statement.
a) We can conclude that M1 prints a 1 and halts only if M accepts w, and thus
the printing problem reduces to the problem of L being recursive
b) We cannot conclude that the printing problem is undecidable
c) We can conclude that the printing problem is recursive but not necessarily
recursively enumerable
d) None of the above.
Q85. The state problem of turing machines is whether a turing machine ever
enters a state q. Ram takes the set L={<M,w>| encoding of turing machine M that
does not accept w} which is known to be undecidable. He modifies M such that in
an accepting state no moves are made. Shyam further modifes M to M1 so that in
an accepting state it moves to state q and then halts. Choose the correct
statement.
a) We can conclude that M1 halts only if M accepts w, and thus the state problem
reduces to the problem of L being recursive
b) We cannot conclude that the printing problem is undecidable
c) We can conclude that the printing problem is recursive but not necessarily
recursively enumerable
d) None of the above.
Q86. The printing problem of turing machines is whether a turing machine ever
prints a 111 on its tape. Ram takes the set L={<M,w>| encoding of turing machine
M that does not accept w} which is known to be undecidable. He modifies M such
that in an accepting state no moves are made. Shyam further modifes M to M1 so
that in an accepting state it prints a 111 and then halts. Choose the correct
statement.
a) We can conclude that M1 prints a 111 and halts only if M accepts w, and thus
the printing problem reduces to the problem of L being recursive
b) We cannot conclude that the printing problem is undecidable
c) We can conclude that the printing problem is recursive but not necessarily
recursively enumerable
d) None of the above.
Q87. The blank tape halting of turing machines is whether a turing machine
started on blank tape halts. Ram takes the set L={<M,w>| encoding of turing
machine M that does not accept w} which is known to be undecidable. He modifies
M such that in an accepting state no moves are made. Shyam further modifes M to
M1 so that it starts with a blank tape and first prints w on the tape and
behaves just like M. Choose the correct statement.
a) We can conclude that M1 halts only if M accepts w, and thus the printing
problem reduces to the problem of L being recursive
b) We cannot conclude that the printing problem is undecidable
c) We can conclude that the printing problem is recursive but not necessarily
recursively enumerable
d) None of the above.
Q88. The aim of the following questionis to prove that the language {M| M is
the code of a turing machine which, irrespective of the input, halts and outputs
a 1, is undecidable. This is to be done by reducing from the language {M�,x|M�
halts on x}, which is known to be undecidable.
Ram proceeds as follows. He takes the turing machine M and modifies it so that
it makes no moves in its final state and then it prints a 1 in the final state
and halts. Shyam further modifies this M so that it initially takes an arbitrary
turing machine M� and its input x, and if M� accepts and halts on x then M will
start its operation otherwise not. This he achieves by having M enumerate turing
machines and strings till the encoding for M� and x are obtained.
Choose the correct statement
a) the modified M will accept all strings and print a 1 provided M halts on w,
but we have a decision problem for M� then we can resolve whether M halts on w
b) M� is always recursive and the modified M accepts a recursive language
c) The above argument shows that M� is recursively enumerable
d) The above argument shows that M� is recursive but not necessarily context
sensitive
Q89. The emptiness problem for r.e. sets is whether for any r.e. set L we can
decide if L=j . As L is a subset of {a} we conclude that
a) L does not satisfy the containment property so L cannot be r.e.
b) L is a regular set as {a} is regular
c) L is recursive always
d) L is recursively enumerable
Q90. The completeness problem for r.e. sets is whether for any r.e. set L we
can decide if L=S *.
a) as no finite subset of L can be the same as L we conclude that the set L is
not r.e.
b) L is r.e. as L is regular
c) L is recursively enumerable as we only require a turing machine that halts on
all inputs
d) L is recursive but not necessarily context-free
Q91. The regularity problem for r.e. sets is whether for any r.e. set L, is L
regular?
a) the regularity problem is decidable
b) as the regular sets are contained in the context-free languages if the
regularity problem is decidable then by the containment property every cfl must
be regular
c) every r.e. set is trivially seen to be regular as every turing machine has a
finite control
d) as every regular set is contained in the set of all strings, the latter must
be in L by the containment property and that is known to be undecidable.
Q92. The context-freeness problem for r.e. sets is whether for any r.e. set L,
is L context-free?
a) the context-freeness problem is decidable
b) as the regular sets are contained in the context-free languages if the
regularity problem is decidable then by the containment property every cfl must
be regular
c) every r.e. set is trivially seen to be context-free as every turing machine
has a finite control
d) as every context-free language is contained in the set of all strings, the
latter must be in L by the containment property and that is known to be
undecidable.
Q93. The recusiveness problem for r.e. sets is whether for any r.e. set L, is L
recursiver?
a) the recusiveness problem is decidable
b) as the regular sets are contained in the recursisve if the regularity problem
is decidable then by the containment property every recursive set must be r.e.
c) every recursive set is trivially seen to be regular as every turing machine
has a finite control
d) as every recursive set is contained in the set of all strings, the latter
must be in L by the containment property and that is known to be undecidable.
Q94. Let L0={<M,0>|M is the encoding of a turing machine that accepts the empty
set}
And L1={<M,1>|M is the encoding of a turing machine that does not accept the
empty set}.Let L=L0UL1. Let L� be the complement of L. Choose the correct
statement
a)L is recursively enumerable but not recursive and L� is recursive
b) L is recursive and L� is recursively enumerable
c) L is not recursively enumerable and L� is recursive
d) Neither L nor L� is recursively enumerable
Q95. Let L0={<M,0>|M is the encoding of a turing machine that accepts an
infinite ty set}
And L1={<M,1>|M is the encoding of a turing machine that does not accept an
infinite set}.Let L=L0UL1. Let L� be the complement of L. Choose the correct
statement
a)L is recursively enumerable but not recursive and L� is recursive
b) L is recursive and L� is recursively enumerable
c) L is not recursively enumerable and L� is recursive
d) Neither L nor L� is recursively enumerable
Q96. Let L0={<M,0>|M is the encoding of a turing machine that accepts a
singleton set}
And L1={<M,1>|M is the encoding of a turing machine that does not accept a
singleton set}.Let L=L0UL1. Let L� be the complement of L. Choose the correct
statement
a)L is recursively enumerable but not recursive and L� is recursive
b) L is recursive and L� is recursively enumerable
c) L is not recursively enumerable and L� is recursive
d) Neither L nor L� is recursively enumerable
Q97. Let L0={<M,M�,0>|M,M� are the encodings of turing machines that accept the
empty set}
And L1={<M,M�,1>|M,M� are the encodings of a turing machines that either one or
both do not accept the empty set}.Let L=L0UL1. Let L� be the complement of L.
Choose the correct statement
a)L is recursively enumerable but not recursive and L� is recursive
b) L is recursive and L� is recursively enumerable
c) L is not recursively enumerable and L� is recursive
d) Neither L nor L� is recursively enumerable
Q98. Let L0={<M,0>|M is the encoding of a turing machine that accepts a cfl}
And L1={<M,1>|M is the encoding of a turing machine that does not accept a
cfl}.Let L=L0UL1. Let L� be the complement of L. Choose the correct statement
a)L is recursively enumerable but not recursive and L� is recursive
b) L is recursive and L� is recursively enumerable
c) L is not recursively enumerable and L� is recursive
d) Neither L nor L� is recursively enumerable
Q99. Let L0={<G,G�,0>|G,G� are the encodings of cfgs that generate the same
set}
And L1={<G,G�,1>|G,G� are the encodings of cfgs that either one or both do not
generate the same set}.Let L=L0UL1. Let L� be the complement of L. Choose the
correct statement
a)L is recursively enumerable but not recursive and L� is recursive
b) L is recursive and L� is recursively enumerable
c) L is not recursively enumerable and L� is recursive
d) Neither L nor L� is recursively enumerable
Q100. Let L0={<G,G�,0>|G,G� are the encodings of regular grammars that generate
the same set}
And L1={<G,G�,1>|G,G� are the encodings of regular grammars that either one or
both do not generate the same set}.Let L=L0UL1. Let L� be the complement of L.
Choose the correct statement
a)L is recursively enumerable but not recursive and L� is recursive
b) L is recursive and L� is recursively enumerable
c) L is not recursively enumerable and L� is recursive
