# THEORY OF COMPUTATION(Q141-Q160)

Discussion in 'Electronics Forum' started by Guest, Apr 5, 2007.

1. ### GuestGuest

THEORY OF COMPUTATION

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

b. Whether the complement of L1 is empty

c. Whether the complement of L1 is infinite

d. Whether L2 intersection L1 is a csl