Matematisk Lingvistik VT97:09

Exercise class 3

Deadline

These exercises are supposed to be handed in on Thursday April 24. These exercises cover chapter 16 from the course book.

Definitions

In these exercises we will use the definitions for one set, two grammars and two trees:

   A = { a , s , t , v }

   G1 is the grammar <VT,VN,S,R> with VT = {a,b} , VN = {S} , 
   S = S and R = { <S,bS> , <S,a> }

   G2 is the grammar <VT,VN,S,R> with VT = {a,b} , VN = {S} , 
   S = S and R = { <S,bSa> , <bS,b> }

   T1 is the tree      S
                      / \
                     b   S
                         |
                         a

   T2 is the tree      S
                      /|\
                     b | S
                        \|
                         a

Furthermore I will assume that you know the following condition for well-formed constituent trees:

Dominance Condition
In any well-formed constituent structure tree, for any sister nodes x and y, there does not exist a node z such that both x dominates z and y dominates z.

This tree constraint is not in the course book but we have dealt with it in the lectures.

Exercises

1. Give an example of a string with length 5 over alphabet A and show also the reverse of this string.

2. Can a language over alphabet A contain the string avstavats? And can it contain the string avstavar? Explain your answers.

3. Give a derivation of the string bbba for grammar G1.

4. Is T1 a well-formed constituent tree? Explain your answer.

5. What ordered pairs of nodes are in the command relation for tree T1?

6. Can grammar G1 generate tree T1? Can grammar G2 generate the string ba?

7. Determine if the grammars G1 and G2 are type 3, type 2, type 1 or type 0 (more than one positive answer per grammar possible).

8. Describe in words the languages generated by grammar G1 and grammar G2.

9. Is T2 a well-formed constituent tree? Explain your answer.

10. Write down T1 and T2 according to the formal tree definition outlined on page 441 and 442 of the book. What is the difference between the two tree definitions?

Each exercise is worth 1 point.