Matematisk Lingvistik VT98:12

Exercise class 4

Deadline

These exercises are supposed to be handed in on Tuesday April 28. Late exercises will receive one-point penalty per extra day. The exercises cover sections one, two and three of chapter sixteen of the course book by Partee, Ter Meulen and Wall.

Definitions

In these exercises we will use the definitions for one set A, one grammar G and one tree T:

   A={a,i,n,r,t}
   G is the grammar <VT,VN,S,R> with VT={a,b} , VN={S,A,B} , S=S and 
      R={<S,aB>,<B,bB>,<B,A>,<A,aA>,<A,e>}
   T is the following tree:

      a
     / \
    b   c
    |   |
    d   e

Exercises

1. Notation: (abc)R is the reverse of the string abc and abc-def is the concatenation of the strings abc and def. Now compute ((abc)R-pts)R

2. List four different strings of A*

3. Can the grammar G generate the string e? And can it generate the string a? Can it generate the string b? And can it generate the string aab?

4. The grammar G can derive the string abbaa. Give a derivation for this string. And give the rules you have used for each step in the derivation.

5. What is the dominance relation of tree T?

6. What is the precedence relation of tree T?

7. Is tree T a well-formed tree? Motivate your answer.

8. Give an example of a non-well-formed tree which has a different structure than the examples in the figures 16-2 and 16-3 of the book. Give a reason for this tree not being well-formed.

9. Give a description of the strings that are present in the language generated by grammar G.

10. Make a finite grammar which generates the language consisting of strings which consist of n a's where n is any nonnegative number not equal to one: L={e,aa,aaa,aaaa,aaaaa,...}

Each exercise is worth one point.