91Ó°ÊÓ

Let $\mathit{I}\mathit{N}\mathit{F}\mathit{I}\mathit{N}\mathit{I}\mathit{T}{\mathit{E}}_{\mathbf{PDA}}\mathbf{=}\mathbf{\left\{}\left(M\right)\mathbf{|}\mathbf{MisaPDAandL}\left(M\right)\mathbf{isaninfinitelanguage}\mathbf{\right\}}\mathbf{.}$

Show that$\mathit{I}\mathit{N}\mathit{F}\mathit{I}\mathit{N}\mathit{I}\mathit{T}{\mathit{E}}_{\mathbf{P}\mathbf{D}\mathbf{A}}$is decidable.

Let . Show that A is decidable.

Let . Show that A is decidable.

Let $\mathbf{∑}\mathbf{=}\left\{0,1\right\}$.Show that the problem of determining whether a CFG generates some string in ${\mathbf{1}}^{\mathbf{*}}$is decidable. In other words, show that

is a decidable language.

Let is a regular expression describing a language containing at least one string w that has 111 as a substring $\left(\text{i.e.,}w=x111y \text{for} \text{some} x \text{and} y\right)\}$. Show that A is decidable.

Prove that $\mathit{E}{\mathit{Q}}_{\mathbf{D}\mathbf{F}\mathbf{A}}$ is decidable by testing the two DFAs on all strings up to a certain size. Calculate a size that works.

Let C be a language. Prove that C is Turing-recognizable if a decidable language D exists such that .

Let A and B be two disjoint languages. Say that language C separates A and B if $\mathit{A}\mathbf{⊆}\mathit{C}$and $\mathit{B}\mathbf{⊆}\mathit{C}$. Show that any two-disjoint co-Turing-recognizable languages are separable by some decidable language.

Let Show that S is decidable.

Let . Show that$\mathit{P}\mathit{A}{\mathit{L}}_{\mathbf{D}\mathbf{F}\mathbf{A}}$is decidable.