Q1. The following languages are closed under substitution(choose the false statement)

A. regular sets

B. cfls

C. csls

D. recursive sets



Q2. 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



Q3. 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



Q4. 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



Q5. 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



Q6. 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.



Q7. 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.



Q8. 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.



Q9. 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.



Q10. 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



Q11. 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



Q12. 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



Q13. 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



Q14. 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





Q15. 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



Q16. 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



Q17. 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



Q16. 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



Q17. 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



Q18. 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



Q19. 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



Q20. 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