Finite State Automata

Read this article for an example of a finite state machine design of a simple vending machine.A sequential circuit is also called a sequential machine or a finite state machine (FSM) or a finite state automaton. This case study gives an example of the design of a sequential circuit. Each state is assigned a distinct set of 1's and 0's, not using more variables than necessary. Thus 4 states require 2 variables, 00, 01, 10 and 11. A binary table represents the input/output behavior of the circuit. We use a sequential circuit, because the output also depends on the state. Recall that state requires memory (that is, flip flops). Thus, a binary table with entries that give the output and next state for given inputs and current state represents the design of the machine. A finite state machine diagram can also represent the design: circles represent states; arrows represent transitions next to states; and inputs and outputs label the arrows (sometimes written as input/ output). Finally, Boolean equations can also represent the design. Lastly, Karnaugh maps or Boolean logic rules can be used to simplify (or minimize) the equations, and thus the design.

Finite State Automaton, also named finite-state machines, are just a special type of graph. In defining them we will again use set theory, showing the wide utility of sets.

A Finite State Automaton is a tuple (S, I, O, ns, o), where S is a finite set of state, I is a finite set of input symbols, O is a finite set of output symbols, ns a function from S x I to S is the next state function, and o is a function from S to O is the output function. There is a distinguished state, so, which is the initial or starting state. An example of a finite state automaton is given in the next paragraph.

Assume a simple vending machine that takes a quarter, button-on, and "cup full" as inputs, and coffee as output. This is a minimal 'no frills' vending machine. We give a graph representation of this machine, its state transition diagram which describes the behavior of the machine.

Finite State Automaton Given by a Transition Diagram

Instruction: For each state we draw a vertex or node. The input function maps a state and an input to a next state. For each such state and input we draw an arc to the node that the input function maps to. The resulting diagram is as follows:

Note that the "/" in the Coffee / Dispense state. The state is written above the "/" and the output is written below. Dispense is short-hand for dispense the cup and the coffee into the cup.

Generating Finite State Automaton from Next-State Tables

A finite state machine can be represented via a graph diagram, as above, or equivalently using a table. Given the diagram one can construct the next state table; conversely, given the next state table one can draw the state diagram.

The next state table for the above diagram is as follows:

We constructed the table by reading the entries from the next-state diagram. For example, in the diagram, there is an arc that connects the "OFF" state with the "ON" state, labeled "quarter." Hence, we enter "quarter" into the cell having row labeled OFF and column labeled Input.

The reverse process of drawing the transition diagram from a given next-state table is similar, but in reverse. Draw a node for each state in the table; for the above table, the states are the labels of the rows and the labels of the Next State column. Draw an arc for each entry in a cell whose row is a Current State and whose column is Next State. The label on the arc is the entry in the Input column for that Current State and Next State. In each Current State node for which there is an entry in the Output column, write the corresponding entry below the name of the Current State node after a "/.

Source: Saylor Academy
Creative Commons License This work is licensed under a Creative Commons Attribution 4.0 License.

Last modified: Thursday, 9 July 2020, 12:52 AM