WPI Worcester Polytechnic Institute

Computer Science Department
------------------------------------------

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.

Additional Problem for Students taking the course for Graduate Credit

  1. (10 points) Problem 5.22 from textbook (Rice's Theorem).

Homework Submission