Matematisk Lingvistik VT96:15

Class:   15
Date:    960222
Topic:   Exercise class 5

Exercise class 5

These exercises are supposed to be handed in on Monday February 26.

In these exercises we will use the following basic structures and definitions:

T is the tree:

   a
  / \
 b   c
    / \
   d   e

G is the grammar <VT,VN,S,R> with VT = {a,b} , VN = {A,B,S} , S = S and R = { <S,ASB> , <S,e> , <A,aaa> , <B,b> }
ab-cd means the concatenation of the strings ab and cd
(ab)R means the reversal of the string ab

1. Compute (ab-(cd)R)R

2. An infix is a substring which is neither a prefix nor a suffix. Give a prefix, a suffix and an infix for the string abcdfg.

3. Will the grammar G generate the string e? And what about ab? And aab? And aaab?

4. The grammar G can derive the string aaaaaabb. Give a derivation for this string.

5. Is it possible to make a tree for the derivation of the string aaaaaabb by G? If your answer is yes, give the tree. Otherwise give a reason for this not being possible.

6. Compute the dominance relation for tree T.

7. Compute the precedence relation for tree T.

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 grammar which generates the language: {e,ab,abab,ababab,abababab,...}

Each exercise is worth 1 point.