CSE 237, Spring 2006
Homework 10
due 4/24/06 in class

• Do not submit problems whose answers are in the textbook

• Start each problem on a new sheet.

Problem 1. Decidable questions about context-free languages (answers in textbook)

(a) 4.9

(b) 4.13

Problem 2. EQ_CFG

(a) Show that EQ_CFG is co-recognizable

(b) Prove that EQ_CFG is not decidable. 
Hint: use a reduction from ALL_CFG, defined on p. 197 of the textbook

(c) We have proved in class that EQ_REX is decidable.  Explain why an analogous proof of the decidability of EQ_CFG would not work.

(d) What can we conclude about EQ_CFG based (a) and (b)? Explain.

Problem 3.  Undecidable questions

(a) Let us define CONTEXT_FREE_TM as follows:

CONTEXT_FREE_TM = {<M>: M is a TM which accepts a context-free language}.

Show that CONTEXT_FREE_TM is not decidable. 
Hint: this is analogous to the proof that REGULAR_TM is not decidable, see textbook section 5.1.

(b) Problem 5.12

(c) Problem 5.13