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 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 "m raise to 5" is accepted by this NFA." Once we have the NFA, we use the algorithm of automata Theory to convert it into a regular expression. The language it represents tell 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 3 coins are tails. There are eight possible state: HHH, HHT, ... TTT. The only - is HHH, the only + is TTT. Draw this NFA, labeling any edge that can flip between states with the letter m.
Convert this NFA into regular expression. Is m raise to 3 in the language of this machine? THe Shortest word in this language is the shortest solution of this puzzle. What is it?
