Matematisk Lingvistik VT98:24

Exercise class 8

Deadline

These exercises are supposed to be handed in on Friday May 29. Late exercises will receive a one-point penalty per extra day. The exercises cover chapter nineteen of the course book by Partee, Ter Meulen and Wall.

Definitions

In these exercises we will use the definitions for two languages L1 and L2, one Turing machine TM and one type 0 grammar G.

   L1 contains strings of a's and b's, starting with an a and  
      ending with a b: a(a\/b)*b

   L2 contains strings of equally many a's as b's and equally many c's
      as b's with first the a's and b's in any order and then all c's

   G  is the grammar <VT,VN,S,R> with VT={a,b} , VN={S,A,B,C,D} , 
      S=S and R={<S,DCD>,<C,ABC>,<C,e>,<BA,AB>,
                 <BD,Db>,<DA,aD>,<DD,a>}

   TM is the Turing machine <K,E,d,s> with K={q0,q1,q2} , E={a,b,#} , 
      s=q0 and d={(q0,a,q0,R),(q0,b,q1,R),(q1,a,q2,R),(q1,b,q1,R),
                  (q2,a,q2,R),(q2,b,q2,b)}

Exercises

1. Give two strings that are accepted by Turing machine TM. Also give two strings that are rejected by TM.

2. Give derivations (sequences of situations) for the two accepted strings you presented in the previous question.

3. Describe the language that is accepted by Turing machine TM.

4. Make a Turing machine that accepts language L1.

5. Some language L is Turing decidable. Does that mean that L is in the range of some partial recursive function? Motivate your answer.

6. Give two strings that can be generated by grammar G. Furthermore give two strings that cannot be generated by this grammar.

7. Give derivations for the two strings in the previous question that G could generate.

8. Describe the language that is accepted by grammar G.

9. Create a type 0 grammar that generates language L2.

10. Prove that the question L=Ø is undecidable if L is an arbitrary Turing acceptable language. Hint: use the undecidability of the Halting Problem.

Each exercise is worth one point.