1

I have enrolled into course of computational methods, and currently we are reviewing automata and regular expressions. In one of the course assignments we were asked to design a finite state automata that models the payment process of a vending machine.

For our base model they told us that the vending machine works with coins of $1, $2, $5, $10, $20, and $50, and that the final state is a product worth $80. At first I was very shocked because I thought that I would have to draw all the possible paths (combinations) of coin insertions; for example, if someone wants to pay the $80 with only $1 coins I would need an automaton with over 80 states.

Now, here's the deal. Our teacher told us that of course it is a valid way of doing the automaton, but a rather overcomplicated and inefficient one. What he really expects is that we make a generalization of the automaton and he gave us the following hint:

"If the design of the automaton works with the numbers of the coins (denominations) so that the state you are in also tells you how much money you have accumulated, then you have already found a way to generalize for any scenario".

Note: He also gave us this image, he told us that it might give a little push towards the solution:

Hint

Our automaton's final test is that it can work with ANY currency system, fictional or real. For example a currency that has coins of $3, $16 $47 $64, or Japanese currency system: ¥1, ¥5, ¥10, ¥50, ¥100, ¥500, ¥1000, ¥2000, ¥5000, and ¥10000.

Any ideas/suggestions on how to draw/design the automaton? I mean, I seriously don't believe I would have to draw more than 10000 states if I want to represent Japan's currency system.

Arturo Olivares
  • 45
  • 4

1 Answers1

0

You need exactly 81 states to solves this problem. Consider each state corresponds how much money is deposited so far. The final state is actually shows that there is at least $80 in the machine, it could be more. But we are not going to give change.

There will be 6 arrows going out from each state, one for each type of coin. For instance from state 0, There will be arrows to state 1, state 2, state 5, state 10, state 20 and state 50.

In the final state, the arrows will be self loops.

And you cannot do this with less than 81 states. Basically, in the machine at any time there could be money equal to 0,1,...,80+. Which is in total 81 different case. If you have less than 81 states, it means due pigeon hole principle, at least two cases will be represented by the same state. And there is no way to distinguish them.

Nuri Tasdemir
  • 9,720
  • 3
  • 42
  • 67