Q1. The following problems of r.e. sets are decidable

a. the membership problem

b. the emptiness problem

c.the finiteness problem

d. whether the intersection of two r.e. sets is a language of the same type



Q2. The following problems of r.e. sets are decidable

a. the infiniteness problem

b.the equivalence problem

c. the containment problem

d. whether the union of two r.e. sets is of the same type



Q3. The following problems of r.e. sets are decidable

a. whether the intersection of two r.e. sets is empty

b. whether the r.e. set is equivalent to a given regular set

c. whether the r.e. set is regular

d. whether the Kleene closure of a r.e. set is a r.e. set



Q4. The following problems of r.e. sets are decidable

a. whether the complement of a r.e. set is r.e.

b.whether the r.e. set is a csl

c. whether the r.e. set is a cfl

d.whether the reversal of the r.e. set is r.e.



Q5. Choose the correct statement.

The following problems are decidable

a. whether a regular set is finite

b. whether a cfl is regular

c. whether a csl is a cfl

d. whether a recursive set is a csl



Q6. Choose the correct statement

The following problems are decidable


a. whether a dcfl is finite

b. whether a recursive set is a cfl

c. whether a r.e. set is a csl

d. whether a r.e. set is a dcfl



Q7. The following problems are decidable

Choose the correct statement

a. whether a dcfl is r.e.

b. whether a recursive set is regular

c. whether a recursive set if regular but not infinite

d. whether a r.e. set is a dcfl that is infinite



Q8. The following problems are NP-complete.(Choose the correct one).

a. 1SAT

b. 2SAT

c. 3SAT

d. hamiltonian circuit problem where the graph does not have more than 100^1000 nodes



Q9. The following problems are not NP-complete. (Choose the correct one).

a. 0/1 knapsack problem

b. node cover problem with the graphs having more than 100^100 nodes

c.edge cover problem with graphs having edges more than 100^100 nodes

d. travelling salesman problem with the number of nodes in the graph restricted to 100^100 nodes



Q10. The following problems are not NP-complete.(Choose the correct one).

a. the partition problem

b. the chromatic number problem

c. the integer programming problem

d. the all pairs shortest path problem



Q11. Choose the false statement

The following can be effectively enumerated

a. finite automata

b.deterministic push down automata

c. push down automata

d. halting turing machines