Homework 4 (due 10/11)
CS344/444


We finished Sections 5.7 and 5.8; I mentioned transducers (covered in Section 5.9) and went on to talk about regular expressions, Section 6.1, 6.3 (also see Appendix O). I stated Kleene's Theorem (Section 6.2), we will see the proof next week and continue to talk about regular languages (chapters 6 and 7).

 For the time being we skipped some attractive material in chapter 5: bidirectional transducers, stochastic automata and Büchi automata. I'm definitely planning to come back to the later subject.

The midterm will be in 6th week, 90 minutes beginning of class (open book, open notes). If you want me to review particular material, please let me know by the weekend.

Homework is due at the beginning of next class for in-class students and by midnight for OL students.


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


1. [Reading Assignment] Read Sections 5.7.2., 5.8, 5.9, and 6.1. of the book.

2.  [Minimizing DFSM, 12pt] Minimize the following automaton using the procedure we saw in class (using k-equivalence of states; you won't have to go deeper than k = 3 in this example). Show the result for each k = 0, 1, ... separately.

3. [Regular Expressions, 3pt] Write a (Javascript/Perl/etc.) regular expression that recognizes valid dates in the range 1900-2099 in the formats mm/dd/yyyy and yyyy/mm/dd. As separators allow /, -, and a space. Depending on which language you use, test your expression (there are many Javascript regular expression testers out on the web).

4. [(Formal) Regular Expressions, 16pt] Do Exercise 6.2, g), h), q), and r), page 152. Hint: the word aaa contains two occurrences of aa.

5. [Extra Credit] A word is square-free if it does not contain a subword of the form ww; e.g. 012021 is square-free, but 1002 (w=0) and 210102 (w=10)are not. How long a square-free word can you build on 3 letters (0,1,2)?

6. [Extra Cedit, Transducer, 9pt] Here's a simplified description of one mode of writing text on a cell-phone: 1 = _, 2 = abc, 3 = def, 4 = ghi, 5 = jkl, 6 = mno, 7 = pqrs, 8 = tuv, 9 = wxyz. If you press 2 once you get an a, if you press it twice you get a b, if you press it three times a c (and similarly for the other numbers). If you want to spell ba, you press 2 twice, wait, and then press 2 again. Model this behavior by a transducer (see Section 5.9). I.e. you want to write a transducer that as input takes something like 222p2p777p and outputs "car" (use p for pause and to end the text). Don't implement the full transducer, just implement the subset taking as input 2, 3, 7 and p (for pause/end). Hint: this is a bit trickier than it looks at first, since, in a way, you need to look ahead; e.g. after you've read 2 from the input, you can't right away output a, since the next symbol might be another 2. Maybe start with just two symbols: p and 2.

Note: As usual, use jflap to implement the transducer (select Mealy or Moore machine, depending on which one you think will work better) and run a test-suite.



Marcus Schaefer
Last updated: October 5th, 2010.