Matematisk Lingvistik VT96:18

Class:   18
Date:    960229
Topic:   Exercise class 6

Exercise class 6

These exercises are supposed to be handed in on Monday March 4.

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

T is the tree:

    S
   / \
  NP  VP
  |   |
  N   V
  |   |
John sings

M1 is the automaton defined by: K = {s0,s1}, Sigma = {a,b}, Delta = { <s0,a,s0> , <s0,b,s1> , <s1,a,s1> , <s1,b,s1> }, q0 = s0 and F = {s0}
M2 is the automaton defined by: K = {s0,s1,s2}, Sigma = {a,b}, Delta = { <s0,a,s1> , <s1,bb,s2> , <s1,bbb,s2> , <s2,a,s1> }, q0 = s0 and F = {s1}

1. Give all pairs <x,y> of terminal nodes in tree T for which x commands y.

2. Give a context free grammar that generates the language that is defined by the regular expression a*b*.

3. Give a regular grammar that generates the language that is defined by the regular expression a*b*.

4. Give an arbitrary context free grammar which is not a context sensitive grammar.

5. Draw the automata M1 and M2.

6. Is automaton M1 a dfa? Is it an ndfa? What about automaton M2?

7. What language will be accepted by automaton M1? And what by automaton M2?

8. Give a regular expression describing the language accepted by automaton M1 and one for the language accepted by automaton M2.

9. We create an automaton M1' which is identical to M1 except that F'=Sigma-F. What language does M1' accept?

10. Based on exercise 9: can you draw a general conclusion about what will happen to a language accepted by an automaton of the class of automaton M1 if you change the set of final states in such way that F'=Sigma-F?

Each exercise is worth 1 point.