CSE 3502, Fall 2017
Homework 9

due 11/29/17 in class


Problem 1. EQCFG


(a)   Prove that EQCFG is co-recognizable
Hint: define the complement of EQCFG , and make use of a decider for ACFG to show that it
's recognizable


(b)   Prove that EQCFG is not decidable. 
Hint: use a reduction from ALLCFG, defined on p. 225 of the textbook (where it
's also proved to be undecidable)


(c)    We have proved in class that EQREX is decidable (it's also in the textbook).  Explain why an analogous proof of the decidability of EQCFG would not work.


(d)   Using (a) and (b), prove that EQCFG is not recogizable.


(e)    We've shown in class that the complement of ATM is not recognizable. Use this fact together with result (a) above to prove that there can be no mapping reduction from ATM to EQCFG


Problem 2. Applying Rice's theorem

(a)    Let us define CFTM as follows:

CFTM = {<M>: M is a TM and L(M) is context-free }.

Can we use Rice's theorem to prove CFTM is undecidable? Justify carefully.

(b) Can we use Rice's theorem to show that EQTM is undecidable? Explain.


Problem 3. Post Correspondence Problem (PCP)

(a) Problem 5.3

(b) Prove that PCP is recognizable.
Hint: how can we use enumeration to find a match if one exists?