Matematisk Lingvistik VT98:15

Exercise class 5

Deadline

These exercises are supposed to be handed in on Tuesday May 5. Late exercises will receive a one-point penalty per extra day. The exercises cover sections 3.3, 4 and 5 of chapter sixteen and sections 1 and 2 of chapter seventeen of the course book by Partee, Ter Meulen and Wall.

Definitions

In these exercises we will use the definitions for the language L, the grammar G, the finite automaton FA and the tree T:

          n n
   L = { a b  } = {e,ab,aabb,aaabbb,...}
   G is the grammar <VT,VN,S,R> with VT={b,c,d} , VN={S,A} , S=S and 
      R={<S,bAc>,<bAc,bcd>,<A,e>}
   FA is the finite automaton <K,E,d,q0,F> with K={q0,q1,q2} , q0=q0 ,
      E={a,b,c} , F={q0,q1} and d={(q0,a,q0),(q0,b,q0),(q0,c,q1),
                                   (q1,a,q2),(q1,b,q2),(q1,c,q1),
                                   (q2,a,q2),(q2,b,q2),(q2,c,q2)}
   T is the following tree:

           S
          / \
         NP  VP
        /|    |
     DET N    V
     |   |    |
   the  man   laughs

Exercises

1. Give an example element of the belongs relation for tree T. And present a pair of nodes that are clause mates in tree T. Furthermore give an example of an element of the commands relation for tree T.

2. Tree T has been generated with a context-free grammar. What rules of the grammar have been used for producing this tree?

3. What is the grammar type of grammar G? Note that a grammar can have more than one type.

4. What is the language type of the language produced by grammar G? Note that a language can have more than one type.

5. Draw a state diagram for finite automaton FA.

6. Is finite automaton FA deterministic, nondeterministic or both?

7. Determine which of the strings in the set {e,abc,cba,ccc} will be accepted by finite automaton FA.

8. Describe the language that is accepted by finite automaton FA.

9. Prove that the language described by the regular expression ((a\/b)\/c)*d is a regular language by using the inductive definition of regular languages presented in definition 17.10 on page 463 in the course book (a\/b is the union of {a} and {b}).

10. Can language L be represented with a regular expression? Motivate your answer.

Each exercise is worth one point.