Homework 3 (due 10/4) CS344/444

Amber covered Section 5.4, 5.7, and 5.8.

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.

2. [DFSM, 6pt]

(i) Do Exercise 5.8 (a) on page 123 of the book.

(ii) Build a NFSM for the same language.

3. [NFSM and DFSM, 14pt] Convert the first and second NFSMs (labeled (a) and (b)) in Exercise 5.9 on page 123 of the book into (deterministic) FSMs.

4. [Minimal DFSMs, 15pt] Do Exercise 5.11. a), d), e) (page 124 of the book). Do both parts (i) and (ii) [if appropriate] for each of them.

5. [Extra Credit, hard] A set of numbers A is eventually periodic if there is a number p (the period) and some number n so that m is in A if and only if m+p in A, for all m ≥ n. E.g., 1, 5, 10, 11, 20, 21, 30, 31, 40, 41, ... is eventually periodic with period 10 starting at n = 10. Show that a language L over the single-letter alphabet {a} is regular if and only if the set of lengths of strings in L: A = {|w|: w in L} is eventually periodic.

Marcus Schaefer
Last updated: September 28th, 2010.