14. Label vertices with two numbers, the first |w|mod 3, the second |w|mod 5.
Then the states labeled 03, 20, etc. are made final states.
23. (a) By contradiction. Suppose G M has no cycles in any path from the
initial state to any final state. Then every walk has a finite number of
steps, and so every accepted string has to be of finite length. But this
implies that the language is finite.
(b) Also by contradiction. Assume that GM has some cycle in a path from
the initial state to some accepting state. We can then use the cycle to
generate an arbitrarily long walk labeled with an accepted string. But a
finite language cannot contain arbitrarily long strings.
25. There are many different solutions. Here is one of them.
Section 2.2
3. The complement of the language in Figure 2.8 is {a n : n is odd. n ≠ 3} ∪ {λ}.
A dfa for this language is
Note that you cannot just complement the final state set in Figure 2.8.
5.
.
8. A four-state solution is trivial, but it takes a little experimenting to get a threestate one. Here is one answer:
Then the states labeled 03, 20, etc. are made final states.
23. (a) By contradiction. Suppose G M has no cycles in any path from the
initial state to any final state. Then every walk has a finite number of
steps, and so every accepted string has to be of finite length. But this
implies that the language is finite.
(b) Also by contradiction. Assume that GM has some cycle in a path from
the initial state to some accepting state. We can then use the cycle to
generate an arbitrarily long walk labeled with an accepted string. But a
finite language cannot contain arbitrarily long strings.
25. There are many different solutions. Here is one of them.
Section 2.2
3. The complement of the language in Figure 2.8 is {a n : n is odd. n ≠ 3} ∪ {λ}.
A dfa for this language is
Note that you cannot just complement the final state set in Figure 2.8.
5.
.
8. A four-state solution is trivial, but it takes a little experimenting to get a threestate one. Here is one answer: