FSM Exercise 1

The Better Cola Machine*

Starting from the Cola Machine example, consider a more sophisticated machine that returns change. The basic specification is just like the original machine (it accepts the same coins) except that:

Your task is to draw this better Cola Machine using extra states and arcs. The only fundamental change is that we will allow arcs to accept coins (input) and give change (output).  We will do this by allowing labels on top of the arcs to denote coins accepted, whilst labels underneath the arc will denote change given.

*this example comes from the book Finite State Morphology by Beesley and Karttunen (CSLI Publications, Stanford 2003)