Decidability

ᴬ Answer all parts for the following DFA $M$ and give reasons for your answers.

Consider the problem of determining whether a DFA and a regular expression are equivalent. Express this problem as a language and show that it is decidable.

Let $\operatorname {ALL}_{\text{DFA }}=\left\{ \langle A\rangle \mid A \text{ is a DFA and } L(A)=\Sigma^{*}\right\}$. Show that $\operatorname {ALL}_{\text{DFA }}$ is decidable.

Let $A \varepsilon_{\mathrm{CFG}}=\left\{ \langle G\rangle \mid G\text{ is a CFG that generates }\varepsilon \right\}$. Show that $A \varepsilon_{\mathrm{CFG}}$ is decidable.

ᴬ Let $E_{\mathrm{TM}}=\left\{ \langle M\rangle \mid M\text{ is a TM and }L(M)=\emptyset \right\}$. Show that $\overline{E_{\mathrm{TM}}}$, the complement of $E_{\mathrm{TM}}$, is Turing-recognizable.

Let $X$ be the set $\left\{ 1,2,3,4,5\right\}$ and $Y$ be the set $\left\{ 6,7,8,9,10\right\}$. We describe the functions $f: X \longrightarrow Y$ and $g: X \longrightarrow Y$ in the following tables. Answer each part and give a reason for each negative answer.

Let $\mathcal{B}$ be the set of all infinite sequences over $\left\{ 0,1\right\}$. Show that $\mathcal{B}$ is uncountable using a proof by diagonalization.

Let $T=\left\{ (i, j, k) \mid i, j, k \in \mathcal{N}\right\}$. Show that $T$ is countable.

Review the way that we define sets to be the same size in Definition 4.12 (page 203). Show that "is the same size" is an equivalence relation.

ᴬ Let $\operatorname {INFINITE}_{\text{DFA }}=\left\{ \langle A\rangle \mid A\text{ is a DFA and }L(A)\text{ is an infinite language }\right\}$. Show that $\operatorname {INFINITE}_{\text{DFA }}$ is decidable.

Let $\operatorname {INFINITE}_{\text{PDA }}=\left\{ \langle M\rangle \mid M\text{ is a PDA and }L(M)\text{ is an infinite language }\right\}$. Show that $\operatorname {INFINITE}_{\text{PDA }}$ is decidable.

ᴬ Let $A=\left\{ \langle M\rangle \mid M\text{ is a DFA that doesn't accept any string containing an odd number of 1 s}\right\}$. Show that $A$ is decidable.

Let $A=\left\{ \langle R, S\rangle \mid R\text{ and }S\text{ are regular expressions and }L(R) \subseteq L(S)\right\}$. Show that $A$ is decidable.

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

is a decidable language.

• Show that the problem of determining whether a CFG generates all strings in $1^{*}$ is decidable. In other words, show that $\left\{ \langle G\rangle \mid G \text{ is a CFG over } \left\{ 0,1\right\} \text{ and } 1^{*} \subseteq L(G)\right\}$ is a decidable language.

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

Prove that $\operatorname {EQ}_{\text{DFA }}$ 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 iff a decidable language $D$ exists such that $C=\left\{ x \mid \exists y(\langle x, y\rangle \in D)\right\}$.

• Prove that the class of decidable languages is not closed under homomorphism.

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

Let $S=\left\{ \langle M\rangle \mid M \text{ is a DFA that accepts } w^{\mathcal{R}} \text{ whenever it accepts } w\right\}$. Show that $S$ is decidable.

Let $\operatorname {PREFIX-FREE}_{\text{REX }}=\left\{ \langle R\rangle \mid R\text{ is a regular expression and }L(R)\text{ is prefix-free }\right\}$. Show that $\operatorname {PREFIX-FREE}_{\text{REX }}$ is decidable. Why does a similar approach fail to show that $\operatorname {PREFIX-FREE}_{\mathrm{CFG}}$ is decidable?

• ᴬ Say that an NFA is ambiguous if it accepts some string along two different computation branches. Let $\operatorname {AMBIG}_{\text{NFA }}=\left\{ \langle N\rangle \mid N\text{ is an ambiguous NFA }\right\}$. Show that $\operatorname {AMBIG}_{\text{NFA }}$ is decidable. (Suggestion: One elegant way to solve this problem is to construct a suitable DFA and then run $E_{\text{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.

• ᴬ Let $\operatorname {BAL}_{\text{DFA }}=\left\{ \langle M\rangle \mid M\text{ is a DFA that accepts some string containing an equal number of 0s and 1s}\right\}$. Show that $\operatorname {BAL}_{\text{DFA }}$ is decidable. (Hint: Theorems about CFLs are helpful here.)

• Let $\operatorname {PAL}_{\text{DFA }}=\left\{ \langle M\rangle \mid M\text{ is a DFA that accepts some palindrome }\right\}$. Show that $\operatorname {PAL}_{\text{DFA }}$ is decidable. (Hint: Theorems about CFLs are helpful here.)

• Let $E=\left\{ \langle M\rangle \mid M\text{ is a DFA that accepts some string with more 1s than 0s}\right\}$. Show that $E$ is decidable. (Hint: Theorems about CFLs are helpful here.)

Let $C=\left\{ \langle G, x\rangle \mid G\text{ is a CFG }x\text{ is a substring of some }y \in L(G)\right\}$. Show that $C$ is decidable. (Hint: An elegant solution to this problem uses the decider for $E_{\text{CFG }}$.)

Let $C_{\text{CFG }}=\left\{ \langle G, k\rangle \mid G\text{ is a CFG and }L(G)\text{ contains exactly }k\text{ strings where }k \geq 0\text{ or }k=\infty \right\}$. Show that $C_{\mathrm{CFG}}$ is decidable.

Let $A$ be a Turing-recognizable language consisting of descriptions of Turing machines, $\left\{ \left\langle M_{1}\right\rangle ,\left\langle M_{2}\right\rangle , \ldots \right\}$, where every $M_{i}$ is a decider. Prove that some decidable language $D$ is not decided by any decider $M_{i}$ whose description appears in $A$. (Hint: You may find it helpful to consider an enumerator for $A$.)

Say that a variable $A$ in CFL $G$ is usable if it appears in some derivation of some string $w \in G$. Given a CFG $G$ and a variable $A$, consider the problem of testing whether $A$ is usable. Formulate this problem as a language and show that it is decidable.

The proof of Lemma 2.41 says that $(q, x)$ is a looping situation for a DPDA $P$ if when $P$ is started in state $q$ with $x \in \Gamma$ on the top of the stack, it never pops anything below $x$ and it never reads an input symbol. Show that $F$ is decidable, where $F=\left\{ \langle P, q, x\rangle \mid (q, x)\text{ is a looping situation for }P\right\}$.