CS344/444

We talked about Regular Expressions (Chapter 6) in class (though I did not go into material from Sections 6.3/6.4), we covered Regular Grammars (Chapter 7) and we started the discussion of regular/non-regular languages proving the famous pumping lemma (Sections 8.1-8.4). I mentioned an interesting theory related blog by Richard Lipton. He has posted a couple of times on automata; one interesting post was about intersections of regular languages.

Next week will be the midterm, 90 minutes (open book, open notes). After that we will talk about Büchi automata (which the book covers earlier in Section 5.12). We'll probably see some additional material which will come from the book by Khoussainov/Nerode on automata theory.

For this homework you have until the week after the midterm, so it includes some questions that require material we'll cover on 10/18.

**Submission**: you can submit the homework by hardcopy
in class or by sending it to me as an email.

1. [Reading Assignment] Read Sections 8.1-8.5.

2. [Regular Expressions to FSM, 4pt] Do Exercise 6.7 (b), page 153.

3. [And back again, 8pt] Convert the FSM in Example 6.9 (page 141) into a regular expression (following the procedure we saw in class). Note that in this particular example there is no need to add a new start or accepting state, since the present start and accepting states are good: the start state has no incoming transitions, and the accepting state has no outgoing transitions.[

4. [Regular Grammars, 8pt] Regular grammars allow rules of the form X -> ε, X -> a and X -> aY, where X, Y are nonterminals and a is a letter of the alphabet.

- Prove or disprove: if
*instead*of X -> aY we have rules of the form X -> Ya, the resulting grammars still accept precisely the regular languages. - Prove of disprove: if we allow both rules of the form X ->aY and X ->Ya, the resulting grammars still accept precisely the regular languages.

5. [Regular and nonregular languages, 10pt] Do Exercises 8.1 b, f, i, n
(page 182/183) of the book. *Hint*: (i) is nasty. Leave it to the end and
think about it carefully.

6. [Büchi Automata, 6pt] Do Exercise 5.20 b) and c) (page 126).

7. [Extra Credit] Show that there are languages A and B that can each be
accepted by FSMs with at most O(n) states, but whose intersection requires
Ω(n^{2}) states.

8. [Extra Credit, hard] Prove the following statement: Given languages L, A and B (over the same alphabet) so that A does not contain ε, show that if

L = AL u B

then L = A^{*}B.

9. [Extra Credit, harder] Can you use the previous statement
to convert deterministic FSMs into regular expressions. *Hint*: go
through regular grammars.

Marcus Schaefer

Last updated: October 13th, 2010.