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 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 Show that S is decidable.

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

Let $\mathit{E}\mathbf{=}\{M|M$ is a DFA that accepts some string with more 1s than 0s}. Show that E is decidable. (Hint: Theorems about CFLs are helpful here.)

Let $\mathbf{PREFIX}−{\mathbf{FREE}}_{\mathrm{REX}}=$role="math" localid="1659933266276" $\mathbf{\left\{}\mathbf{\left\{}\mathbf{R}\mathbf{\right\}}\mathbf{|}\mathbf{R}\mathbf{}\mathbf{is}\mathbf{}\mathbf{a}\mathbf{}\mathbf{regular}\mathbf{}\mathbf{expression}\mathbf{}\mathbf{and}\mathbf{}\mathbf{L}\mathbf{\left(}\mathbf{R}\mathbf{\right)}\mathbf{}\mathbf{is}\mathbf{}\mathbf{prefix}\mathbf{-}\mathbf{free}\mathbf{\right\}}$. Show that $\mathbf{PREFIX}\mathbf{−}{\mathbf{FREE}}_{\mathbf{REX}}$is decidable. Why does a similar approach fail to show that$\mathbf{PREFIX}\mathbf{−}{\mathbf{FREE}}_{\mathbf{CFG}}$ is decidable?

Say that an NFA is ambiguous if it accepts some string along two different computation branches

$\mathbf{Let}{\mathbf{AMBIG}}_{\mathrm{NFA}}\mathbf{=}\mathbf{\left\{}\mathbf{\left(}\mathbf{N}\mathbf{\right)}\mathbf{|}\mathbf{N}\mathbf{is}\mathbf{an}\mathbf{ambiguous}\mathbf{NFA}\mathbf{\right\}}\mathbf{.}$Show that${\mathbf{AMBIG}}_{\mathrm{NFA}}$ is decidable. (Suggestion: One elegant way to solve this problem is to construct a suitable DFA and then run ${\mathbf{E}}_{\mathrm{DFA}}$on it.)

A useless state in a pushdown automaton is never entered on any input string. Consider the problem of determining whether a pushdown automaton has any useless states. Formulate this problem as a language and show that it is decidable