Matematisk Lingvistik VT96:24

Class:   24
Date:    960314
Topic:   Exercise class 8

Exercise class 8

These exercises are supposed to be handed in on Monday March 18. You can put them in my mailbox across room B390 in HSC. You can get the exercises back from Thursday March 21 at room B382.

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
A* means the Kleene star operator applied to A
context-free grammar G defined by VN = {S,A,C}, VT = {a,b,c}, S = S and R contains the rules S->aAbCc, A->aA, A->b, C->Cc and C->b.

1. Will grammar G generate e? What about abc? And abbc? and aaabbbccc?

2. Give a derivation by grammar G for the string abbbc or a tree created by G for the same string.

3. Give a description of the strings generated by grammar G.

4. Make a pda that accepts the language generated by grammar G.

5. Will it be possible to make a finite automaton that accepts the language generated by grammar G? If your answer is yes give such an automaton. If your answer is no state why.

6. We choose two arbitrary context-free languages A and B. Will A' \/ B* be a context-free language?

7. We choose two arbitrary context-free languages A and B. Will A' /\ B* be a context-free language?

8. We choose two arbitrary context-free languages A and B. Is it general possible to find out if A=B? (the answer is in the book)

9. Prove that the language of strings with n a's followed by n+m b's followed by m c's is context-free.

10. Prove that the language of strings with n a's followed by a string containing n b's and n c's in any order is not context-free. (Examples: aabccb and aaacbcbbc. Strings always start with n a's)

Each exercise is worth 1 point.