Matematisk Lingvistik VT97:18

Exercise class 6

Deadline

These exercises are supposed to be handed in on Tuesday May 27. They cover chapter 19 of the course book.

Definitions

In these exercises we will use definitions for one Turing machine and one type 0 grammar:

   TM1 is the Turing Machine <K,Sigma,s,delta> with K = {q0,q1} , 
   Sigma = {a,b,#} , s = q0 and delta = { <q0,a,q1,R> , <q0,b,q0,b> ,
   <q1,a,q1,a> , <q1,b,q0,R> }

   G1 is the type 0 grammar <VT,VN,S,R> such that VT = {a,b} ,
   VN = {A,C,D,S} , S=S and R = { <bA,Ab> , <C,AC> , <C,bC> ,
   <C,e> , <DA,aD> , <D,e> , <S,DC> }

Exercises

1. Give two strings from {a,b}* that are accepted by TM1 and give two strings from {a,b}* that are rejected by TM1.

2. Give the TM1 acceptance sequence of situations for one of the accepted strings from exercise 1.

3. Describe the language that TM1 accepts.

4. Create a type 0 grammar which generates exactly the same language as TM1 accepts.

5. Give two strings from VT* that are generated by G1 and give two strings from VT* that are rejected by G1.

6. Give the G1 derivation for one of the accepted strings from exercise 5.

7. Describe the language that G1 accepts.

8. Create a Turing machine which accepts exactly the same language as G1 generates.

9. Consult the tables on page 561 in the book to find a class of languages C for which all of the following is true: C is closed under union but not under complementation and the membership question is decidable for C but the question L(G)=Sigma* is undecidable.

10. Use the undecidability of the Halting Problem to prove that the question L=Ø is undecidable if L is a language accepted by an arbitrary Turing machine.

Each exercise is worth 1 point.