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.

1. [Reading Assignment] Read Sections 5.6, 5.7.1 of the book.

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.