Q141. The following languages are closed under substitution(choose the false
statement)
A. regular sets
B. cfls
C. csls
D. recursive sets
Q142. Choose the false statement. The reversal of a dcfl L is
a. never r.e.
b. is always r.e.
c. is always a cfl
d. is always a csl
Q143. Choose the false statement. The reversal of a dcfl L is
a. always a dclf
b. always a cfl
c. always a recursive set
d. always a r.e. set
Q144. Choose the false statement. The union of two dcfls is
a. never r.e.
b. is always r.e.
c. is always a cfl
d. is always a csl
Q145. Choose the false statement. The union of two dcfls is
a. always a dclf
b. always a cfl
c. always a recursive set
d. always a r.e. set
Q146. The intersection of two cfls can simulate an arbitrary turing machine
computation, and this can be used to show some problems are undecidable. The
intersection of two cfls is (choose the false statement)
a. never regular
b. never a cfl
c. never a csl
d. always not r.e.
Q147. The intersection of two dcfls can simulate an arbitrary turing machine
computation, and this can be used to show some problems are undecidable. The
intersection of two dcfls is (choose the false statement)
a. never regular
b. never a cfl
c. never a csl
d. always not r.e.
Q148. The intersection of two csls can simulate an arbitrary turing machine
computation, and this can be used to show some problems are undecidable. The
intersection of two csls is (choose the false statement)
a. never a recursive set
b. never a cfl
c. never a csl
d. always not r.e.
Q149. It is not known at present if the csls are closed under complement. The
complement of a csl(choose the false statement) is
a. never a cfl
b. never a csl
c. never a recursive set
d. may be a set which is not r.e.
Q150. The shuffle of languages L1 and L2 is obtained by shuffling the words of
L1 with that of L2. Choose the false statement
a. the shuffle of two regular sets is regular
b. the shuffle of two cfls is a cfl
c. the shuffle of a cfl and a regular set is a cfl
d. the shuffle of a regular set and a cfl may be regular
Q151. The following problems are decidable
a. whether a turing machine has at least three states
b. whether a turing machine will ever halt
c. whether a turing machine will ever print a symbol
d. whether a turing machine will ever enter a designated state
Q152. The following problems are decidable
a. whether a turing machine ever leaves a particular cell it it scanning
b.whether a turing machine started on blank tape will ever halt
c. whether a turing machine accepts at least two strings
d. whether a turing machine accepts a finite set
Q153. The following problems are decidable
a. whether the tape alphabet has at least two symbols
b. whether a turing machine with 12 tapes will accept an infinite set
c. for ever string w the turing machine accepts it also accepts wR.
d. whether a turing machine will ever print three consecutive 1's
Q154. Let L1={<M>| M is the encoding of a finite auotmaton} and w is a string in
(0+1)*. Let L2={<M>| M is the encoding of a turing machine}. The following
problems are decidable(choose the false statement)
a. Whether L1 contains w
b. Whether L1 is empty
c. Whether L1 is infinite
d. Whether L2=L1
Q155. Let L1={<M>| M is the encoding of a finite auotmaton} and w is a string in
(0+1)*. Let L2={<M>| M is the encoding of a turing machine}. The following
problems are decidable(choose the false statement)
a. Whether L1 contains all strings over the termainal vocabuary
b. Whether L1 is empty and regular
c. Whether L1 is infinite
d. Whether L2 is contained in L1
Q156. Let L1={<M>| M is the encoding of a finite auotmaton} and w is a string in
(0+1)*. Let L2={<M>| M is the encoding of a turing machine}. The following
problems are decidable(choose the false statement)
a. Whether the complement of L1 contains w
b. Whether the complement of L1 is empty
c. Whether the complement of L1 is infinite
d. Whether L2 intersection L1 is empty
Q157. Let L1={<M>| M is the encoding of a finite auotmaton} and w is a string in
(0+1)*. Let L2={<M>| M is the encoding of a finite machine}. The following
problems are decidable(choose the false statement)
a. Whether the complement of L1 contains w
b. Whether the complement of L1 is empty
c. Whether the complement of L1 is infinite
d. None of the above
Q156. Let L1={<M>| M is the encoding of a dpda} and w is a string in (0+1)*. Let
L2={<M>| M is the encoding of a dpda machine}. The following problems are
decidable(choose the false statement)
a. Whether the complement of L1 contains w
b. Whether the complement of L1 is empty
c. Whether the complement of L1 is infinite
d. Whether L2 intersection L1 is infinite
Q157. Let L1={<M>| M is the encoding of a dpda} and w is a string in (0+1)*. Let
L2={<M>| M is the encoding of a dpda}. The following problems are
decidable(choose the false statement)
a. Whether the complement of L1 contains w
b. Whether the complement of L1 is empty
c. Whether the complement of L1 is infinite
d. Whether L2 is contained in L1
Q158. Let L1={<M>| M is the encoding of a dpda} and w is a string in (0+1)*. Let
L2={<M>| M is the encoding of a dpda}. The following problems are
decidable(choose the false statement)
a. Whether the complement of L1 contains w
b. Whether the complement of L1 is empty
c. Whether the complement of L1 is infinite
d. Whether L2 intersection L1 is empty
Q159. Let L1={<M>| M is the encoding of a dpda} and w is a string in (0+1)*. Let
L2={<M>| M is the encoding of a dpda}. The following problems are
decidable(choose the false statement)
a. Whether the complement of L1 contains w
b. Whether the complement of L1 is empty
c. Whether the complement of L1 is infinite
d. Whether L2 intersection L1 is a dcfl
Q160. Let L1={<M>| M is the encoding of a dpda} and w is a string in (0+1)*. Let
L2={<M>| M is the encoding of a dpda}. The following problems are
decidable(choose the false statement)
a. Whether the complement of L1 is contained in L2
