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
-------------
For More Sample Papers Visit:
http://onestopgate.com/gate-preparation/ - http://onestopgate.com/gate-preparation/
|