THEORY OF COMPUTATION 4
THEORY OF COMPUTATION 4
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’,xM’ 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 contextfree
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 contextfree 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 contextfreeness problem for r.e. sets is whether for any r.e. set L, is L contextfree?
a) the contextfreeness problem is decidable
b) as the regular sets are contained in the contextfree 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 contextfree as every turing machine has a finite control
d) as every contextfree 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
d) Neither L nor L’ is recursively enumerable
