Exercises

Show that $\operatorname {EQ}_{\text{CFG }}$ is undecidable.

Show that $\operatorname {EQ}_{\mathrm{CFG}}$ is co-Turing-recognizable.

Find a match in the following instance of the Post Correspondence Problem.

If $A \leq_{\mathrm{m}} B$ and $B$ is a regular language, does that imply that $A$ is a regular language? Why or why not?

ᴬ Show that $A_{\mathrm{TM}}$ is not mapping reducible to $E_{\mathrm{TM}}$. In other words, show that no computable function reduces $A_{\text{TM }}$ to $E_{\text{TM }}$. (Hint: Use a proof by contradiction, and facts you already know about $A_{\text{TM }}$ and $E_{\text{TM }}$.)

ᴬ Show that $\leq_{\mathrm{m}}$ is a transitive relation.

ᴬ Show that if $A$ is Turing-recognizable and $A \leq_{\mathrm{m}} \bar{A}$, then $A$ is decidable.

ᴬ In the proof of Theorem 5.15, we modified the Turing machine $M$ so that it never tries to move its head off the left-hand end of the tape. Suppose that we did not make this modification to $M$. Modify the PCP construction to handle this case.