Q181. 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
Q182. 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
Q183. 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
Q184. 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.
Q185. 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
Q186. 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
Q187. 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
Q188. 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
Q189. 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
Q190. 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
Q191. 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
Q192. Choose the false statement
The following can be effectively enumerated
a. deterministic linear bounded automata
b. linear bounded automata
c.halting turing machines
d. turing machines
Q193. choose the false statement
The following can be effectively enumerated
a. multidimensional turing machines
b. multitrack turing machines
c. multiheaded turing machines
d. halting turing machines
Q194. Choose the false statement
The following can be effectively enumerated
a. finite sets
b. regular sets
c. dcfls
d. recursive sets
Q195. Choose the false statement
The following can be effectively enumerated
a. cfls
b.csls
c. recursive sets
d. r.e. sets
Q196. Choose the false statement
The following can be effectively enumerated
a. type-0 grammars
b. halting turing machines
c. type-1 grammars
d. type 2 grammars
Q197. Choose the false statement
The following can be effectively enumerated
a. type-0 grammars
b. halting turing machines
c. type-1 grammars
d. type 3 grammars
Q198. Ram and Shyam define universal languages as follows
L0={<M,x,1>|M is the encoding of a turing machine that accepts x}
L00={<M,x,1>|M is the encoding of a halting turing machine that accepts x}
L1={<M,x,1>| M is the encoding of a linear bounded automata that accepts x}
L2={<M,x,1>| M is the encoding of a push down automata that accepts x}
L22={<M,x,1>| M is the encoding of a dpda that accepts x}
L3={<M,x,1>| M is the encoding of a fa that accepts x}
Choose the correct statement
a. all the universal languages are r.e.
b. the complements of all the universal languages are r.e.
c. all the universal languages are recursive
d. except L00 all the universal languages are r.e.
Q199. Ram and Shyam define universal languages as follows
L0={<M,x,1>|M is the encoding of a turing machine that accepts x}
L00={<M,x,1>|M is the encoding of a halting turing machine that accepts x}
L1={<M,x,1>| M is the encoding of a linear bounded automata that accepts x}
L2={<M,x,1>| M is the encoding of a push down automata that accepts x}
L22={<M,x,1>| M is the encoding of a dpda that accepts x}
L3={<M,x,1>| M is the encoding of a fa that accepts x}
Choose the correct statement
a. all the universal languages are recursive.
b. the complements of all the universal languages are recursive
c. all the universal languages are r.e.
d. except L00 all the universal languages are r.e.
Q200. Ram and Shyam define universal languages as follows
L0={<G,x,1>|G is the encoding of a type 0 that generates x}
L00={<G,x,1>|G is the encoding of a type 0 grammar that generates a recursive
set and generates x}
L1={<G,x,1>| G is the encoding of a type 1 grammar that generates x}
L2={<G,x,1>| G is the encoding of a type 2 grammar that generates x}
L22={<G,x,1>| G is the encoding of a LR(k) grammar that generates x}
L3={<G,x,1>| G is the encoding of a type 3 grammar that generates x}
Choose the correct statement
a. all the universal languages are r.e.
b. the complements of all the universal languages are r.e.
c. all the universal languages are recursive
d. except L00 all the universal languages are r.e.
Result Page:- 1-20 |
21-40 |
41-60 |
61-80 |
81-100 |
101-120 |
121-140 |
141-160 |
161-180 |
181-200 |
201-220 |
221-240 |
|