Question

Construct a finite-state machine that models an old-fashioned soda machine that accepts nickels, dimes, and quarters. The soda machine accepts change until 35 cents has been put in. It gives change back for any amount greater than 35 cents. Then the customer can push buttons to receive either a cola, a root beer, or a ginger ale.

Short answer

The finite-state machine that models an old-fashioned soda machine is shown below:

Step-by-step solution

General form

Finite-State Machines with Outputs (Definition):

A finite-state machine\({\bf{M = }}\left( {{\bf{S,}}\,\,{\bf{I,}}\,\,{\bf{O,}}\,\,{\bf{f,}}\,\,{\bf{g,}}\,\,{{\bf{s}}_0}} \right)\)consists of a finite set S of states, a finite input alphabet I, a finite output alphabet O, a transition function f that assigns to each state and input pair a new state, an output function gthat assigns to each state and input pair output and an initial state\({{\bf{s}}_0}\).

Formulae to be used:

1 Nickels = 5 cents

1 Dimes = 10 cents

1 Quarters = 25 cents

Step 2: Construct a finite-state machine model

Given that an old-fashioned soda machine that accepts nickels, dimes, and quarters. The soda machine accepts change until 35 cents has been put in.

It gives change back for any amount greater than 35 cents. Then the customer can push buttons to receive either a cola, a root beer, or a ginger ale.

Construction:

Let us consider the states\({{\bf{s}}_{\bf{i}}}\), where\({\bf{i = 0,1,2,3,4,5,6,7}}\).

The states will represent that the machine contains 0, 5, 10, 15, 20, 25, 30, and 35 cents respectively.

If we add a nickel to the machine, then the input is 5 to the current state \({{\bf{s}}_{\bf{i}}}\). We then move to \({{\bf{s}}_{{\bf{i + 1}}}}\) and the output is 0. As we don’t return any money.

If we add a dime to the machine, then the input is 10 to the current state \({{\bf{s}}_{\bf{i}}}\). We then move to \({{\bf{s}}_{{\bf{i + 2}}}}\). If \({{\bf{s}}_{{\bf{i + 2}}}}\) does not exist and the output is the money that gest returned.

If we add a quarter to the machine, then the input is 25 to the current state\({{\bf{s}}_{\bf{i}}}\). We then move to \({{\bf{s}}_{{\bf{i + }}5}}\). If \({{\bf{s}}_{{\bf{i + }}5}}\) does not exist and the output is the money that gest returned.

Let x represent that we hit the button for soda pop. If we are not at state \({{\bf{s}}_7}\), then hitting the button does nothing. If we are at state \({{\bf{s}}_7}\), then we return a soda pop and return at the starting state.

The model of the finite-state machine is shown below:

Therefore, the result shows the required finite-state machine.