### CS4123 Theory of Computation  Homework 3 - D 2002

#### PROF. CAROLINA RUIZ

Due Date: Thursday, April 18th at 5 pm.
Help session: Wednesday, April 17th 5:00-6:30 pm in FL232
Late Policy: No late homework will be accepted

#### Problems

1. (20 points) Prove that the language

EQCFG = { < G1,G2 > | G1 and G2 are CFGs and L(G1) = L(G2)}

is undecidable.

2. (20 points) Prove that the language

CFLTM = { < M > | M is a TM and L(M) is a context free language}

is undecidable.

3. (20 points) Let A and B be two languages over alphabet Sigma. Let AC and BC denote the complements of A and B, respectively.

Prove that if A <=m B then AC <=m BC.

4. (20 points) Let Sigma = {a, b}. Prove that the language

REVTM = { < M > | M is a TM and L(M) ={wwR | w belongs to Sigma*}}

is undecidable.

5. (20 points) Prove that the language

EITM = { < M1,M2 > | M1 and M2 are TMs and the intersection of L(M1) and L(M2) is empty}

1. (20 points) is undecidable, and
2. (10 extra-points) is NOT semi-decidable.