Q101. Let L0={<G,G�,0>|G,G� are the encodings of cfgs that generate infinte
languages}
And L1={<G,G�,1>|G,G� are the encodings of cfgs that either one or both do not
generate infinite sets}.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
Q102. Let L0={<G,G�,0>|G,G� are the encodings of csgs that generate the same
set}
And L1={<G,G�,1>|G,G� are the encodings of csgs that either one or both do
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
Q103. Let L0={<G,G�,0>|G,G� are the encodings of unrestricted grammars that
generate the same set}
And L1={<G,G�,1>|G,G� are the encodings of unrestricted grammars that either one
or both do 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
Q104. Let L0={<G,G�,0>|G,G� are the encodings of linear bounded automata that
generate the same set}
And L1={<G,G�,1>|G,G� are the encodings of linear bounded automata that either
one or both do 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
Q105. Let L0={<G,G�,0>|G,G� are the encodings of unrestricted grammars such that
they generate L and LR respectively with L=LR}
And L1={<G,G�,1>|G,G� are the encodings of unrestricted grammars that generate
languages L and LR with L not the same as LR respectively}.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
Q106. Let L0={<G,G�,0>|G,G� are the encodings of C programs that produce the
same output for all inputs}
And L1={<G,G�,1>|G,G� are the encodings of C programs that do not produce the
same output for all inputs}.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
Q107. Let L0={<G,G�,0>|G,G� are the encodings of C programs that produce some
output for all inputs}
And L1={<G,G�,1>|G,G� are the encodings of C programs that do not produce some
output for all inputs}.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
Q108. Let L0={<G,G�,0>|G,G� are the encodings of C programs that loop on some
input}
And L1={<G,G�,1>|G,G� are the encodings of C programs that do not loop on some
input}.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
Q109. Let L0={<G,G�,0>|G,G� are the encodings of cfgs where the intersection of
the langugaes generated is a cfl}
And L1={<G,G�,1>|G,G� are the encodings of cfgs where the intersection of the
languages generated is not 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
Q110. Let L0={<G,G�,0>|G,G� are the encodings of cfgs that generate regular
sets}
And L1={<G,G�,1>|G,G� are the encodings of cfs that both or either does not
generate a regular 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
Q111. Let L0={<G,G�,0>|G,G� are the encodings of cfgs such that L(G�) is
contained in L(G)}
And L1={<G,G�,1>|G,G� are the encodings of cfgs sucht that L(G�) is not
contained in L(G)}. 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
Q112. Let L0={<G,G�,0>|G,G� are the encodings of cfgs which generate languages
whose complement is also a cfl}
And L1={<G,G�,1>|G,G� are the encodings of C programs that generate languages
whose complement is not both 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
Q113. Let L0={<G,G�,0>|G,G� are the encodings of ambiguous cfgs}
And L1={<G,G�,1>|G,G� are the encodings of unambiguous cfgs}.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
Q114. Let L0={<G,G�,0>|G,G� are the encodings of inherently ambiguous cflss}
And L1={<G,G�,1>|G,G� are the encodings of cfls that are not inherently
ambiguous}.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
Q115. Choose the false statement
a) PCP over a one symbol alphabet is decidable
b) It is undecidable if a csl is a cfl
c) It is undecidable if a turing machine accepts at least 10 inputs
d) It is undecidable if two regular grammars generate the same set
Q116. Define languages L0 and L1 as follows:
L0={<M,M1,0>|M is equivalent to M1}
L1={<M,M1,1>| M is not equivalent to M1}
Here <M,w,I> is a triplet, whose first component, M is an encoding of a turing
machine , second component M1 is the encoding of a nondeterministic linear
bounded automaton, and third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L� is not
(b) L� is recursively enumerable but L is not
(c) Both L and L� are recursive
(d) Neither L nor L� is recursively enumerable
Q117. Define languages L0 and L1 as follows:
L0={<M,M1,0>|M is equivalent to M1}
L1={<M,M1,1>| M is not equivalent to M1}
Here <M,w,I> is a triplet, whose first component, M is an encoding of a turing
machine , second component M1 is the encoding of a 100 tape nondeterministic
turing machine that halts on all inputs, and third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L� is not
(b) L� is recursively enumerable but L is not
(c) Both L and L� are recursive
(d) Neither L nor L� is recursively enumerable
Q118. Define languages L0 and L1 as follows:
L0={<M,w,0>|M in the course of its computation visits state w}
L1={<M,w,1>| M does not halt visit state w}
Here <M,w,I> is a triplet, whose first component, M is an encoding of a
nondeterministic 789 pushdown tape machine , second component w, is a state and
third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L� is not
(b) L� is recursively enumerable but L is not
(c) Both L and L� are recursive
(d)Neither L nor L� is recursively enumerable
Q119. Define languages L0 and L1 as follows:
L0={<M,w,0>|M prints symbol w}
L1={<M,w,1>| M never prints symbol w}
Here <M,w,I> is a triplet, whose first component, M is an encoding of a
nondeterministic 789 pushdown tape machine , second component w, is a symbol and
third component I is a bit.
Let L=L0 U L1. Which of the following is true?
(a) L is recursively enumerable but L� is not
(b) L� is recursively enumerable but L is not
(c) Both L and L� are recursive
(d)Neither L nor L� is recursively enumerable
Result Page:- 1-20 |
21-40 |
41-60 |
61-80 |
81-100 |
101-120 |
|
