Matematisk Lingvistik VT96:21

Class:   21
Date:    960307
Topic:   Exercise class 7

Exercise class 7

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

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

A /\ B means the intersection of A and B
A \/ B means the union of A and B
language L is the complement of {aaa} (alphabet={a,b})
pda P defined by K = {q0,q1,q2}, Sigma = {a,b}, Gamma = {A}, initial state is q0, F = {q2} and Delta = { (q0,aaa,e)->(q1,A) , (q1,a,e)->(q1,A) , (q1,b,A)->(q2,e) , (q2,b,A)->(q2,e) }

1. Proof that the language consisting of all strings which contain n a's followed by 2*n b's is not a regular language.

2. Proof that the language consisting of all strings which contain n a's followed by any number of b's is a regular language.

3. We have three regular languages A, B and C. Will the language (A \/ B) /\ (A /\ C) also be a regular language? Give a reason for your answer.

4. Make a finite state automaton that accepts language L.

5. Will it be possible to make a Type 3 grammar that accepts language L? If you think that it is possible, give the grammar. Otherwise give a reason for why this is not possible.

6. Will it be possible to make a Type 3 grammar that accepts language of the strings containing n a's followed by n b's? If you think that it is possible, give the grammar. Otherwise give a reason for why this is not possible.

7. Is pda P deterministic or is it non-deterministic?

8. Will pda P accept the string e? Will it accept aaa? Will it accept aaab? And what about aaabb?

9. Give a pda-P-derivation (that is a list of situations) for all legal strings you have found in the previous exercise.

10. Give a type 2 grammar for the language that will be accepted by pda P.

Each exercise is worth 1 point.