Q161. Let L1={<M>| M is the encoding of a pda} and w is a string in (0+1)*. Let
L2={<M>| M is the encoding of a pda}. 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 intersection L1 is empty
Q162. Let L1={<M>| M is the encoding of a pda} and w is a string in (0+1)*. Let
L2={<M>| M is the encoding of a pda}. 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 contains all strings over the terminal vocabulary
Q163. Let L1={<M>| M is the encoding of a pda} and w is a string in (0+1)*. Let
L2={<M>| M is the encoding of a pda}. 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
Q164. Let L1={<M>| M is the encoding of a pda} and w is a string in (0+1)*. Let
L2={<M>| M is the encoding of a pda}. 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 is contained in L1
Q165. Let L1={<M>| M is the encoding of a pda} and w is a string in (0+1)*. Let
L2={<M>| M is the encoding of a finite automata}. 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
Q166. Let L1={<M>| M is the encoding of a pda} and w is a string in (0+1)*. Let
L2={<M>| M is the encoding of a pda}. 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 intersection L1 is empty
Q167. Ram comes up with a universal language for cfls, Lucfl={<M,x>|M is the
encoding of a pda that accepts w}. Choose the correct statement
a.Lucfl is a decidable language
b. Lucfl is partially decidable but not decidable
c.Lucfl is not partially decidable
d. Lucfl cannot exist
Q168. Ram comes up with a universal language for dcfls, Ludcfl={<M,x>|M is the
encoding of a dpda that accepts w}. Choose the correct statement
a.Ludcfl is a decidable language
b. Ludcfl is partially decidable but not decidable
c.Ludcfl is not partially decidable
d. Ludcfl cannot exist
Q169. Ram comes up with a universal language for labas, Lulba={<M,x>|M is the
encoding of a lba that accepts w}. Choose the correct statement
a.Lulba is a decidable language
b. Lulba is partially decidable but not decidable
c.Lulba is not partially decidable
d. Lulba cannot exist
Q170. Ram comes up with a universal language for turing machines, Lu={<M,x>|M is
the encoding of a turing that accepts w}. Choose the correct statement
a.Lu is a decidable language
b. Lul is partially decidable but not decidable
c.Lul is not partially decidable
d. Lul cannot exist
Q171. Ram comes up with a universal language for halting turing machines,
Lu={<M,x>|M is the encoding of a halting turing machine that accepts w}. Choose
the correct statement
a.Lu is a decidable language
b. Lu is partially decidable but not decidable
c.Lu is not partially decidable
d. Lu cannot exist
Q172. Let L0={<M,w,0>| M is the encoding of a pda that halts on input w} and let
L1={<M,x,1>| M is the encoding of a pda that does not halt on input w}
Define a language L=L0UL1.
What can be said about L?
a. L is decidable
b. L is partially decidable but not decidable
c. L is not partially decidable
d. L is accepted by a pda
Q173. Let L0={<M,w,0>| M is the encoding of a lba that halts on input w} and let
L1={<M,x,1>| M is the encoding of a lba that does not halt on input w}
Define a language L=L0UL1.
What can be said about L?
a. L is decidable
b. L is partially decidable but not decidable
c. L is not partially decidable
d. L is accepted by a pda
Q174. The following problems of csls are decidable
a. the equivalence problem
b.the containment problem
c. the membership problem
d. the completeness problem
Q175.The following problems of csls are decidable
a. the emptiness problem
b.the finiteness problem
c. the infiniteness problem
d. whether the intersection of two csls is a csl
Q176. The following problems of csls are decidable
a. the equivalence problem
b. whether the intersection of two csls is empty
c. the regularity problem
d. whether the complement of a csl is a recursive set
Q177. The following problems of recursive sets are decidable
a. the membership problem
b. the emptiness problem
c.the completeness problem
d. the finiteness problem
Q178. The following problems of recursive sets are decidable
a. the infiniteness problem
b. the equivalence problem
c. the containment problem
d.whether the complement is recursive
Q179. The following problems of recursive sets are decidable
a. whether the recursive language is equal to a regular set R
b. the regularity problem
c. the equivalence problem
d. the completeness problem
Q180. The following problems of recursive sets are decidable
