Matematisk Lingvistik VT97:15

Exercise class 5

Deadline

These exercises are supposed to be handed in on Thursday May 15. They cover chapter 17 from section 17.3.1 (page 475) and chapter 18.

Notation

Because of the limitation of the range of characters in HTML I cannot display every character I need. I will use the following replacements in this exercise:

   A \/ B     the union of A and B
   A /\ B     the intersection of A and B

Definitions

In these exercises we will use definitions for two pushdown automata:

   PDA1 is the pushdown automaton <K,Sigma,Gamma,Delta,s,F> with
   K = {q0} , Sigma = {a,b,c} , Gamma = {A,C}, s = q0 , F = {q0} 
   and delta = { <q0,a,e,q0,A> , <q0,b,e,q0,A> , <q0,c,e,q0,C> , 
                 <q0,a,C,q0,e> , <q0,b,C,q0,e> , <q0,c,A,q0,e> }

   PDA2 is the pushdown automaton <K,Sigma,Gamma,Delta,s,F> with
   K = {q0,q1} , Sigma = {a,b,c} , Gamma = {A,B}, s = q0 , F = {q1} 
   and delta = { <q0,a,e,q0,A> , <q0,b,e,q0,B> , <q0,c,e,q1,e> , 
                 <q1,a,A,q1,e> , <q1,b,B,q1,e> }

Exercises

1. Draw the state diagram for PDA1 and draw the state diagram for PDA2.

2. Determine for PDA1 and PDA2 whether they are deterministic, non-deterministic or both.

3. Give two strings from Sigma* that are accepted by PDA1 and give two strings from Sigma* that are rejected by PDA1. Do the same for PDA2.

4. Describe the language that PDA1 accepts and describe the language accepted by PDA2.

5. Create a context free grammar which generates exactly the same language as PDA1 accepts. Do the same for the language accepted by PDA2.

6. Draw the state diagram for a deterministic pushdown automaton which accepts the language abc(abc)* (strings containing one or more successive sequences abc).

7. The languages F1, F2 and F3 are regular languages. Will ( F1 /\ F2 ) \/ F3 be a regular language? Motivate your answer.

8. The languages C1, C2 and C3 are context free languages. Will ( C1 /\ C2 ) \/ C3 be a context free language? Motivate your answer.

9. Apply the pumping theorem for context free languages to the language:

    n 2n
   a b  
   

   (the language of strings starting with n a's (n>=0) followed by 2*n b's). What do you conclude from the result?

10. Apply the pumping theorem for context free languages to the language:

     n 2n n
    a b  c
    

    (the language of strings starting with n a's (n>=0) followed by 2*n b's followed by n c's). What do you conclude from the result?

Each exercise is worth 1 point.