CSE 2001 Fall 2012 - Tutorial 9

We went over several problems from Tutorial 8.
We also went over the following problems.

1. Is the following language decidable?
   {<M>| M describes a TM with exactly 42 states}

2.  Is the following language decidable?
   {<M>| M describes a TM that decides the Halting Problem}

3. Is the following language decidable?
   {<M>| L(M) is a context-free language}

4.  Prove that EQ_{CFG} is co-TM-recognizable.

5. Prove that decidable languages are closed under intersection.

The following are good practice problems.

1. Problem 4.10 p 211 (Ed 3), 4.9 pg 183 (Ed 2)

2. Problem 4.11 p 211 (Ed 3), 4.10 pg 183 (Ed 2)

3.  Problem 4.10 p 211 (Ed 3), 4.9 pg 183 (Ed 2)

4.  Problem 5.30 p 241 (Ed 3), 5.30  pg 213 (Ed 2). Solve this problem 
without using Rice's Theorem.