Homework 4

Details

1. 1.12 (Notice that it is asking for a DFA (not an NFA) and a regular expression.)
2. 1.18b
3. 1.18c
4. 1.18e
5. 1.19b
6. 1.20c
7. 1.20e
8. 1.20h
9. 1.21b (Show intermediate steps of the procedure)
10. 1.24f
11. 1.24g
12. 1.25
13. 1.39 (Hint: It is not enough to provide an example language for each value of k that seems to require at least k states. You need to be certain that it is impossible to do with k-1.)