Question

Construct a finite-state machine that models a newspaper vending machine that has a door that can be opened only after either three dimes (and any number of other coins) or a quarter and a nickel (and any number of other coins) have been inserted. Once the door can be opened, the customer opens it and takes a paper, closing the door. No change is ever returned no matter how much extra money has been inserted. The next customer starts with no credit.

Short answer

The finite-state machine that models a newspaper vending 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 g that 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 a newspaper vending machine that has a door that can be opened only after either three dimes (any number of other coins) or a quarter and a nickel (and any number of other coins) have been inserted.

Once the door can be opened, the customer opens it and takes a paper, closing the door.

No change is ever returned no matter how much extra money has been inserted. The next customer starts with no credit.

Construction:

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

We arrange the 9 states in 3 rows and 3 columns. The bottom row will represent that a first nickel was inserted and the top row will represent that a first quarter was inserted.

If we add a dime, then we will move to the state to the right or to \({{\bf{s}}_0}\) when it is the third dime.

If we add a nickel, then we move to the state below if no quarter was added previously and no nickel was added previously or we remain at the current state when no quarter was added previously and nickel was added previously or we move to the starting state if a quarter was added previously.

If we add a quarter, then we move to the state above if no nickel was added previously and no quarter was added previously or we remain at the current state when no nickel was added previously and a quarter was added previously or we move to the starting state if nickel was added previously.

Once three dimes or quarter + nickel have been inserted, the customer receives the paper and the algorithm moves back to the start state. Otherwise, the output is always 0 as no money is returned.

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

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