Construct a finite state machine for a pop machine that acce

Construct a finite state machine for a pop machine that accepts nickels, dimes, and quarters. The machine accepts coins until 35 cents has been put in. It gives back change for any amount over 35 cents. then the customer can push buttons to receive either root beer, ginger ale, or cream soda.

Solution

we can identify several key characteristics of a system that can be modeled with a finite state machine: • The system must be describable by a finite set of states. • The system must have a finite set of inputs and/or events that can trigger transitions between states. • The behavior of the system at a given point in time depends upon the current state and the input or event that occur at that time. • For each state the system may be in, behavior is defined for each possible input or event. • The system has a particular initial state. Let us consider another example of a system that can be described by a finite state machine — an old, mechanical soda machine. This machine dispenses only 1 kind of soft drink at the price of $0.30 each. It accepts only nickels, dimes, and quarters and automatically returns change for any amount deposited over $0.30. The machine has 2 buttons — one for dispensing a drink; the other to return the deposited coins. Because this is a purely mechanical system, it does not have a memory system, nor can it directly perform arithmetic operations like addition or subtraction. We begin our analysis of this system by identifying the possible inputs to the soda machine: nickel (N), dime (D), quarter (Q), dispense button (DB), and coin return (R). To identify possible states for the machine, start with the states we can get to by depositing a single coin. We can label these states with the value, in cents, of the coins deposited so far: 5, 10, and 25. We illustrate our model thus far in Figure 3. Next, we can think about what happens when we deposit a nickel in addition to the first coin. The resulting model is shown in Figure 4. We continue this expansion until we have identified the minimal set of states that lead to a total of at least $0.30, but are less than $0.55 (since depositing a quarter after 30 cents has been deposited will return the quarter immediately without changing the state of the machine). We show this version of the FSM in Figure 5. The FSM in Figure 5 covers all possible inputs as long as the sum of the coins previously deposited is less than $0.30. Obviously, the graphical representation of this FSM is quickly becoming hard to handle, so we will introduce an alternative: a tabular representation. We list the states down the left side, and the inputs across the top. The table cell at the intersection of a particular row and column indicates the destination state of the FSM when the column’s input is received when the machine is in the row’s state. °c 2005, David R. Wright CSC216 (Summer 2005) Finite State Machines Page 3 of 28 S 25 10 5 N D Q Figure 3: Start of the Soda Machine FSM Model Q 15 25 30 10 5 S N N N N D Figure 4: Second Phase of the Soda Machine FSM Model However, our FSM is still far from complete! Looking back at the description of the soda machine, we see that the machine will “automatically” return the correct change for and coin deposit that exceeds the price of a soda. To accommodate this behavior, we need to add a few things to our models. First, we need to introduce an input that is really “no input” — in other words, we need to be able to create a trigger so the machine will perform some action without actually receiving an input from the user. We will call this a null input, and will designate it with NULL in the FSM table. To help keep our graphs simple, we will not indicate NULL-input transitions when there is no state change or action performed. Next, we need to define some notation to indicate an action performed by the FSM. In the graphical representation, we will denote such an action that occurs during a transition be following the input symbol with a ‘/’, followed in turn by the action that occurs. This notation is illustrated in Figure 6. In this example, when the FSM is in state S1 and receives input X, the FSM will move to state S2 and perform action(y). In the tabular representation, we will add the action performed in parentheses after the destination state. Table 2 is our tabular representation of the soda machine FSM incorporating our new notation for null inputs and transition actions. However, if we look carefully at this table carefully, we can use our new transition action notation to make a significant simplification of the FSM. Consider the states where coin deposits exceed the price of a soda - our initial design uses extra states and null inputs to create the “automatic” change return functionality required by the description. However, if we use our new action notation, we can make these transitions directly, eliminating 4 states as well as the NULL input symbol. We describe our new FSM graphically in Figure 7 as well as in tabular form in Table 3. (Note that in Figure 7, 4 transitions are labeled with lowercase letters corresponding to the descriptions in the legend below the diagram.) °c 2005, David R. Wright CSC216 (Summer 2005) Finite State Machines Page 4 of 28 Q Q Q Q D Q D N D D D N N N N Q D N 25 20 15 10 5 50 45 40 35 30 S Figure 5: Soda Machine FSM Considering All Valid Coin Inputs Table 1: Tabular Representation of the FSM in Figure 5 N D Q S 5 10 25 5 10 15 30 10 15 20 35 15 20 25 40 20 25 30 45 25 30 35 50 30 35 40 45 50 S1 S2 X / action(y) Figure 6: Denoting a Transition Action in a Graphical FSM Representation Now we’ve established how the soda machine FSM behaves with respect to coin inputs, but we still haven’t modeled how a user actually gets a drink out of the machine! First, however, we will consider the °c 2005, David R. Wright CSC216 (Summer 2005) Finite State Machines Page 5 of 28 Table 2: Updated Tabular Representation of the Soda Machine FSM N D Q NULL S 5 10 25 S 5 10 15 30 5 10 15 20 35 10 15 20 25 40 15 20 25 30 45 20 25 30 35 50 25 30 — — — 30 35 — — — 30 (return(N)) 40 — — — 30 (return(D)) 45 — — — 30 (return(ND)) 50 — — — 30 (return(DD)) Table 3: Minimized Tabular Representation of the Soda Machine FSM N D Q S 5 10 25 5 10 15 30 10 15 20 30 (return(N)) 15 20 25 30 (return(D)) 20 25 30 30 (return(ND)) 25 30 30 (return(N)) 30 (return(DD)) 30 30 (return(N)) 30 (return(D)) 30 (return(Q)) coin-return button, which is supposed to return all coins the user has deposited, or at least a set of coins with the exact same value. Since the machine knows the value of the deposited coins (based on the state it is in), it is straightforward to define the appropriate behavior for the FSM. We simply return a pre-defined combination of coins corresponding to the state the machine is in. This behavior is incorporated into Table 4. Table 4: Final Tabular Representation of the Soda Machine FSM N D Q R DB S 5 10 25 S S 5 10 15 30 S (return(N)) 5 10 15 20 30 (return(N)) S (return(D)) 10 15 20 25 30 (return(D)) S (return(ND)) 15 20 25 30 30 (return(ND)) S (return(DD)) 20 25 30 30 (return(N)) 30 (return(DD)) S (return(Q)) 25 30 30 (return(N)) 30 (return(D)) 30 (return(Q)) S (return(QN)) S (dispense()) Finally, we add the transitions that specify the behavior of the soda machine when the dispense button is pressed. From the description, this button does nothing unless the required amount of money has been deposited into the machine, so our FSM remains in the current state unless it is in the state labeled ‘30’ (the state where 30 cents has been deposited), which triggers the dispensing of a drink, and returns the FSM to °c 2005, David R. Wright CSC216 (Summer 2005) Finite State Machines Page 6 of 28 Q / return(D) D; Q / return(ND) N; D / return(N); Q / return(DD) Q / return(N) N Q (c) (d) D D Q D 30 20 15 (a) (b) 5 (c) (d) 10 (a) (b) 25 N N S N N Figure 7: Minimized Graphical Representation of the Soda Machine FSM the starting state. Table 4 describes the final design of our FSM for the soda machine.