Matematisk Lingvistik VT97:12

Exercise class 4

Deadline

These exercises are supposed to be handed in on Wednesday May 7. They cover chapter 17 until 17.3.1 (page 475) from the course book.

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

Definitions

In these exercises we will use the definitions for two finite automata:

   FA1 is the finite automaton <K,Sigma,delta,q0,F> with
   K = {q0,q1} , Sigma = {a,b} , q0 = q0 , F = { q0 } and
   delta = { <q0,a,q0> , <q0,b,q1> , <q1,a,q1> , <q1,b,q1> }

   FA2 is the finite automaton <K,Sigma,delta,q0,F> with
   K = {q0,q1} , Sigma = {a,b} , q0 = q0 , F = { q0 } and
   delta = { <q0,a,q1> , <q1,b,q0> }

Exercises

1. Draw the state diagram for FA1 and draw the state diagram for FA2.

2. Determine for FA1 and FA2 whether they are deterministic or non-deterministic.

3. Determine if FA1 can produce the strings e, ab, bbaa and abab. Do the same for FA2.

4. Give a regular expression for the language that FA1 accepts. Do the same for the language accepted by FA2.

5. Create a type 3 grammar which accepts exactly the same language as finite automaton F1. Do the same for the language accepted by F2.

6. Prove that the regular expression (ab\/ba)* represents a regular language by using the regular language definition rules (definition 17.10, page 463).

7. Apply the pumping theorem for finite automata 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?

8. Apply the pumping theorem for finite automata languages to the language a*b*. What do you conclude from the result?

9. We create an automaton FA1' which is identical to FA1 except that the new set of final states F' = K-F. Describe in words or with a regular expression the language accepted by FA1'.

10. Based on exercise 9: can you draw a general conclusion about what will happen to a language accepted by an automaton of the class of automaton FA1 (deterministic or non-deterministic) if you change the set of final states in such way that it becomes K-F?

Each exercise is worth 1 point.