*****PLEASE ANSWER ONLY #3 AND #4. IGNORE #2*****

2. (4.13 from the textbook) Let A | R and S are regular expressions and L(R) L(S) Prove that A is decidable. (HINT: Examine the proof that EQDFA is decidable.) 3. Let INFINITETM kM> M is a Turing Machine and the language accepted by M is infinite). Prove that INFINITE- is undecidable. Let STM ( | M is a Turing Machine and M accepts some string from 2*). I M is a Turing 4. a. Explain why the following "proof" that STM is Turing recognizable is incorrect. Proof." Let (wi,w2.wa ) be the list of all strings in * in short lexicographic order (defined on p. 14 of the textbook). Then, the following Turing Machine R is a recognizer for S. On input 1. 2. 3. Set i=1 Simulate the execution of M on wi. If M accepts, accept. Increment i and repeat step 2. Modify this incorrect "proof" to give a correct proof that STM is recognizable. (HINT: Consider the proof that a language is Turing recognizable if and only if some enumerator enumerates it.) b. c. Now, show that ETM | M is a Turing Machine and L(M)is not Turing recognizable 2. (4.13 from the textbook) Let A | R and S are regular expressions and L(R) L(S) Prove that A is decidable. (HINT: Examine the proof that EQDFA is decidable.) 3. Let INFINITETM kM> M is a Turing Machine and the language accepted by M is infinite). Prove that INFINITE- is undecidable. Let STM ( | M is a Turing Machine and M accepts some string from 2*). I M is a Turing 4. a. Explain why the following "proof" that STM is Turing recognizable is incorrect. Proof." Let (wi,w2.wa ) be the list of all strings in * in short lexicographic order (defined on p. 14 of the textbook). Then, the following Turing Machine R is a recognizer for S. On input 1. 2. 3. Set i=1 Simulate the execution of M on wi. If M accepts, accept. Increment i and repeat step 2. Modify this incorrect "proof" to give a correct proof that STM is recognizable. (HINT: Consider the proof that a language is Turing recognizable if and only if some enumerator enumerates it.) b. c. Now, show that ETM | M is a Turing Machine and L(M)is not Turing recognizable