State Diagrams Problem 2

Solution

Self-check

The letters should be on the edges (not in the states). Each edge should have only one letter, not two or three. (e.g. don't combine the c and k transitions into a single edge).

Do you have exactly one start state? Did you mark it with an inward arrow?

You must have at least one end state, but it's ok to have more than one. Make sure they are have the double circle.

In the lower branch, notice that there are two explicit transitions on o, in addition to the loop at the end. This forces the words to include at least two o's.

Count your states: do you have more than 9 (bad)? If so, look for where the above diagram merges two of your states.

Variations

The loop for generating extra o's can be on the final state (as above) or it can be on either of the two previous states. If you put the loop on an earlier state, the two final states can be merged.

The above diagram uses only 8 states. Since you had a limit of 9 you could have had slightly more separate paths. E.g. you might have used different end states for s/bat and s/back.