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
-------------
Want To Crack GATE Click On
www.onestopgate.com
|