Matematisk Lingvistik VT98:21

Exercise class 7

Deadline

These exercises are supposed to be handed in on Tuesday May 19. Late exercises will receive a one-point penalty per extra day. The exercises cover sections three, four, five and six of chapter eighteen of the course book by Partee, Ter Meulen and Wall.

Definitions

In these exercises we will use the definitions for five languages Lm, L1, L2, L3 and L4, and one pushdown automaton PDA:

         n n*m
   Lm = a b    (n*m is the product of n and m; m is a single fixed value)

         n  n
   L1 = a ba

         n n n
   L2 = a b a

         n n n
   L3 = a b a b*

   L4 = { strings consisting of a's, b's and c's in any order but with
          equally many a's as b's }

   PDA is the pushdown automaton <K,E,L,D,s,F> with 
      K={q0,q1} , E={a,b} , L={A,B} , s=q0 , F={q0,q1} and 
      D={(q0,a,e,q0,A),(q0,b,e,q0,B),(q0,e,e,q1,e),
         (q1,a,A,q1,e),(q1,b,B,q1,e)}

Exercises

1. The languages X and Y are context-free. Can we be sure that the intersection of X and Y is context-free? And can we be sure that the union of X and Y is context-free?

2. The languages X and Y are context-free. Can the intersection of X and Y be context-free? And can the union of X and Y be context-free?

3. The language X is context-free. Does that mean that X'' (the complement of the complement of X) is context-free?

4. The languages X and Y are context-free. Is the question "(X\/Y)=Y?" algorithmically solvable? (X\/Y is the union of X and Y)

5. Create a context-free grammar which generates exactly the same language as pushdown automaton PDA accepts. Hint: find out which language PDA accepts and build a grammar for that language.

6. Create a context-free grammar which generates language L4.

7. Apply the pumping theorem for context-free languages to the language L1. What do you conclude from the result?

8. Apply the pumping theorem for context-free languages to the language L2. What do you conclude from the result?

9. Prove that for all possible values of m the language Lm is context-free.

10. Prove that the language L3 is not context-free.

Each exercise is worth one point.