Decidability

Single correct

• ATuring machine $M$ halts on all input strings in $\{0,1\}^*$
• BTuring machine $M$ accepts all input strings in $L$
• CTuring machine $M$ rejects all input strings in $\{0,1\}^* - L$
• DTuring machine $M$ accepts all input strings in $L$ and rejects all input strings in $\{0,1\}^* - L$

Single correct

• AIs $L(G_1) = L(G_2)$?
• BIs $L(G_1) \cap L(G_2) = \emptyset$?
• CIs $L(G_1) = L(R)$?
• DIs $L(G_1) = \emptyset$?

One or more correct

• AEvery subset of a recursively enumerable language is recursive.
• BIf a language $L$ and its complement $\bar{L}$ are both recursively enumerable, then $L$ must be recursive.
• CComplement of a context-free language must be recursive.
• DIf $L_1$ and $L_2$ are regular, then $L_1 \cap L_2$ must be deterministic context-free.

Answer key coming soon

One or more correct

• AGiven two Turing machines $M_1$ and $M_2$, decide if $L(M_1) = L(M_2)$.
• BGiven a Turing machine $M$, decide if $L(M)$ is regular.
• CGiven a Turing machine $M$, decide if $M$ accepts all strings.
• DGiven a Turing machine $M$, decide if $M$ takes more than 1073 steps on every string.

Answer key coming soon

One or more correct

• A$L = \{\langle M \rangle \mid M \text{ is a DFA such that } L(M) = \emptyset\}$
• B$L = \{\langle M \rangle \mid M \text{ is a DFA such that } L(M) = \Sigma^*\}$
• C$L = \{\langle M \rangle \mid M \text{ is a PDA such that } L(M) = \emptyset\}$
• D$L = \{\langle M \rangle \mid M \text{ is a PDA such that } L(M) = \Sigma^*\}$

Answer key coming soon

Single correct

• ABoth $L_1$ and $L_2$ are decidable.
• B$L_1$ is decidable and $L_2$ is undecidable.
• C$L_1$ is undecidable and $L_2$ is decidable.
• DBoth $L_1$ and $L_2$ are undecidable.

Answer key coming soon

Single correct

• AOnly $S_1$ is true.
• BOnly $S_2$ is true.
• CBoth $S_1$ and $S_2$ are true.
• DNeither $S_1$ nor $S_2$ is true.

Answer key coming soon

Single correct

• A$L_1$, $L_3$, and $L_4$ only
• B$L_1$ and $L_3$ only
• C$L_2$ and $L_3$ only
• D$L_2$, $L_3$, and $L_4$ only

Answer key coming soon

Single correct

• AS1 and S2
• BS3 and S4
• CS2 and S3
• DS1 and S4

Single correct

• Aclosed under complementation.
• Bclosed under intersection.
• Ca subset of the set of all recursive languages.
• Dan uncountable set.

Single correct

• AOnly I and II are undecidable
• BOnly III is undecidable
• COnly II and IV are undecidable
• DOnly I, II and III are undecidable

Single correct

• A$f$ is computable if and only if $L_f$ is recursive.
• B$f$ is computable if and only if $L_f$ is recursively enumerable.
• CIf $f$ is computable then $L_f$ is recursive, but not conversely.
• DIf $f$ is computable then $L_f$ is recursively enumerable, but not conversely.

Answer key coming soon

Single correct

• AI and IV only
• BII and III only
• CII, III and IV only
• DIII and IV only

Answer key coming soon

Single correct

• AI and IV only
• BII and III only
• CIII and IV only
• DII and IV only

Answer key coming soon

Single correct

• A$W$ can be recursively enumerable and $Z$ is recursive.
• B$W$ can be recursive and $Z$ is recursively enumerable.
• C$W$ is not recursively enumerable and $Z$ is recursive.
• D$W$ is not recursively enumerable and $Z$ is not recursive.

Answer key coming soon

Single correct

• A$L_1$ is recursive and $L_2, L_3$ are not recursive
• B$L_2$ is recursive and $L_1, L_3$ are not recursive
• C$L_1, L_2$ are recursive and $L_3$ is not recursive
• D$L_1, L_2, L_3$ are recursive

Answer key coming soon

Single correct

• AI only
• BIII only
• CIII and IV only
• DI and IV only

Single correct

• AOnly II
• BOnly III
• COnly I and II
• DOnly I and III

Single correct

• ANeither $L$ nor $\bar{L}$ is recursively enumerable (r.e.).
• BOne of $L$ and $\bar{L}$ is r.e. but not recursive; the other is not r.e.
• CBoth $L$ and $\bar{L}$ are r.e. but not recursive.
• DBoth $L$ and $\bar{L}$ are recursive.

Single correct

• AIf $A \leq_m B$ and B is recursive then A is recursive.
• BIf $A \leq_m B$ and A is undecidable then B is undecidable.
• CIf $A \leq_m B$ and B is recursively enumerable then A is recursively enumerable.
• DIf $A \leq_m B$ and B is not recursively enumerable then A is not recursively enumerable.