Exercises

ᴬ 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.