How do you model a pay phone as a state machine?

Question

I don't understand how a state machine is applied to a problem. In particular - does the model describe every possible permutation of states by definition? How do you incorporate memory that persists and is modified from state to state?

As the most simplistic example let's take only the part of a pay phone that accepts coins and determines if a call can be placed. The cost of a call is 50 cents, nickels, dimes, and quarters are permitted.

Would the state machine be a tree like so:

quarter -> quarter -> valid
quarter -> dime -> dime -> nickel -> valid
dime -> dime -> dime -> dime -> dime -> valid

Or would it be more like:

Accepting_Coins -> Quarter_Inserted -> Add_25c_to_Balance -> Check_balance -> Balance_is_50c -> valid

Accepting_Coins -> Quarter_Inserted -> Add_25c_to_Balance -> Check_balance -> Balance_is_NOT_50c -> Accepting_Coins

Accepting_Coins -> Dime_Inserted -> Add_10c_to_Balance -> Check_balance -> Balance_is_50c -> valid

This second version requires a balance variable in memory.

I want to write event driven programs where an FSM model directs control flow and rejects what I define as invalid event sequences.

Answer 1

As stated in comments, for a pure finite state machine you would need to define each possible amount of money that the pay phone has accepted so far as a state. The acceptance of an inserted coin corresponds to a transition.

Whether or not you need an additional state for "overflow", depends... If the pay phone will reject any coin that does not represent a transition in the model, then you don't need it: the absence of the transition (edge) in the model (graph) would be enough. But in a very detailed implementation, you would also add states for when a coin gets stuck, an invalid coin is inserted, too much is inserted (how will the pay phone respond? will it returned coins, or just returns all of it? ...etc ), a button is pressed, ...

But here is the most basic model:

You probably would also need transitions for dialing, making and ending the call. Once the call ends, you would transition to the state 0 again, so new payments can be accepted.