A one-person game can be converted into an NFA as follows. Let every possible board situation be a state. If any move (there may be several types of moves but we are not interested in distinguishing among them) can change some state x into some state y, then draw an edge from x to y and label it m. Label the initial position - and the winning positions +. "This game can be won in five moves" is the same as saying "m5 is accepted by this NFA." Once we have the NFA we use the algorithm to convert it into a regular expression. The language it represents tells us how many moves are in each winning sequence. Let us do this with the following example. The game of Flips is played with three coins. Initially they are all heads. A move consists of flipping two coins simultaneously from whatever they were to the opposite side. For example, flipping the end coins changes THH into HHT. We win when all three coins are tails. There are eight possible states: HHH, HHT .... TTT. The only - is HHH; the only + is TTT.
(i) Draw this NFA, labeling any edge that can flip between states with the letter m.
(ii) Convert this NFA into a regular expression. Is m3 or m5 in the language of this machine?
(iii) The shortest word in this language is the shortest solution of this puzzle. What is it?