Matematisk Lingvistik VT98:18

Exercise class 6

Deadline

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

Definitions

In these exercises we will use the definitions for three languages L1, L2 and L3, two grammars G1 and G2 and one pushdown automaton PDA:

           n  n n
   L1 = { a bc d } = {b,abcd,aabccdd,aaabcccddd,...}
   L2 = strings of a's, b's and c's in any order but with equally many
        a's as c's
   L3 = (ab)*c*
   G1 is the grammar <VT,VN,S,R> with VT={a,b,c} , VN={S,A,B} , S=S and 
      R={<S,aaA>,<S,bbB>,<A,cA>,<A,aa>,<B,cB>,<B,bb>}
   G2 is the grammar <VT,VN,S,R> with VT={a,b} , VN={S} , S=S and 
      R={<S,aSb>,<S,bSa>,<S,SS>,<S,e>}
   PDA is the pushdown automaton <K,E,L,D,s,F> with 
      K={q0,q1,q2} , E={a,b,c} , L={A,B} , s=q0 , F={q0,q1,q2} and 
      D={(q0,a,e,q0,A),(q0,b,e,q1,B),(q0,c,A,q2,e),(q1,b,e,q1,B),
         (q1,c,B,q2,e),(q2,c,A,q2,e),(q2,c,B,q2,e)}

Exercises

1. Prove that L1 is not a fal.

2. Language L2 contains all strings of format xy*z for x=z=e and y=b. Does this mean that L2 is a fal?

3. Prove that L3 is a fal.

4. Give a finite automaton that accepts the same language as grammar G1 generates.

5. Draw a state diagram for pushdown automaton PDA.

6. Give two strings that are accepted by pushdown automaton PDA. Give also two strings that are rejected by PDA.

7. Give the derivations (=situation sequences) for the two accepted strings you have presented in the previous question.

8. Describe the language that is accepted by pushdown automaton PDA.

9. Give a pushdown automaton that accepts the same language as grammar G2 generates.

10. Prove that there is an algorithmic solution for the question L(FA1)=L(FA2) where FA1 and FA2 are arbitrary finite automata which accept the languages L(FA1) and L(FA2) respectively. Hint: use the closure properties of regular languages and the fact that there is an algorithmic solution for the emptiness question.

Each exercise is worth one point.