CS202 Study Guide
Unit 9: Finite-State Automata
9a. Illustrate abstract machines that can be in exactly one of a finite number of states at any given time
- What is a machine "state"?
- What are applications of finite-state automata?
- What are approaches to visualizing such machines?
- What are the various terms used for "finite-state machine" that one finds in the literature?
As stated in the introduction to this unit: A finite-state machine (FSM), finite-state automaton (FSA), finite automaton, or state machine, is a model that describes an abstract machine. That machine can be in only one of a finite number of states at any point in time. The FSM can change from one state to another as it responds to data inputs that indicate when some condition is satisfied. The change from one state to another is called a transition. An FSM is defined by a list of its states, its initial state, and the conditions for each transition. Often, state machines are illustrated as graphs whose nodes are the states and whose links are the transition conditions.
A "state" is the behavior of a machine at a given moment in time. Machines are capable of only a finite set of behaviors. A state can also be described as the status of a system that is waiting to execute a transition. A transition is a set of actions (behaviors) to be executed when a condition is fulfilled or when an event is detected in the data received. The actions (machine behaviors) triggered by a transition continue until the next transition occurs.
Simple applications of finite-state automata are found in vending machines, which dispense products when the proper combination of coins is deposited; elevators, whose sequence of stops is determined by the floors requested by riders; traffic lights, which change sequence when cars are waiting; and combination locks, which require the input of a sequence of numbers in the proper order.
There are numerous ways to picture (or represent) a state machine: Unified Modeling Language, Specification and Description Language, state/event tables, graphs, etc. Choose the approach that is most understandable for the project at hand. Another choice basis is ready implementation of a model in an automated tool. Preferably, a tool is chosen whose depictions are readily understandable by project personnel.
Review Finite State Machine Overview.
9b. Analyze systems that recognize input patterns, accepting or rejecting an input depending on whether a given pattern occurs
- What is an important personal attribute during technical projects?
- If logical statements can be reduced to an equivalent, is that possible with state machines? How?
- Why is reduction of logical statements and state machines important?
- What are the components of a good state machine specification?
The deeper one goes into technical subjects, the more precise one's terminology must become, and the greater is the attention to detail that one must have. Otherwise, understanding and exposition become increasingly difficult, if not impossible. This is true of the material in this course, and for all technical topics.
We have already seen how logical statements can be reduced so that they are simpler, while yielding the same results. The same is true of state machines. There are two conditions that must hold: 1) each data input while the states are active must lead to equivalent state transitions, and 2) equivalent states will always have the same outputs once the transition occurs. Reduction of logic statements and state machines is important from an implementation, and therefore, cost perspective. A tradeoff with human understandability is made so that cost of construction and ownership can be reduced. However, there is no reason that baseline designs cannot be performed in non-reduced forms, with reduction being made prior to construction.
The course material talks about the components of a state machine specification that can be used for implementation. This author makes some additions from practical experience:
- A set of states, behaviors, the system has to exhibit.
- A set of expected system inputs that are clearly specified.
- A set of outputs the system is supposed to exhibit for each system state.
- Transition rules that cause the system to switch from one state to another.
- A state the system is in when first initialized.
- A clearly specified end-state, if there is one.
- States that exist to handle unexpected inputs, errors, at any given state.
Review Putting the Basics to Use.
9c. Construct discrete-state systems
- What is the difference between Moore and Mealy machines?
- What is similar about Moore and Mealy machines?
- Are the reduction requirements for Moore and Mealy machines the same?
Moore machines have an output that is constant. Once the state is achieved, there can only be one output. However, the state in question can only be achieved when a certain system input is acquired while the system exists in a different specified state. Mealy machines, on the other hand, do not have a constant output. Instead, a state's output depends upon the system input received, while the system is in a prior specific state.
In a very real sense, Moore machines are a special case of Mealy machines. Moore machines accept only one input and deliver one output. Mealy machines accept multiple inputs and deliver multiple outputs. So, Mealy machines are the general case. Moore machines can be developed using the same techniques. Both Mealy and Moore machines can only be in one state at a time, thus the term discrete-state systems.
Optimization for both is the same. One seeks states where: 1) each data input while the states are active must lead to equivalent state transitions, 2) equivalent states will always have the same outputs once the transition occurs. Those states can be combined.
Review Putting the Basics to Use.
9d. Predict how a given system will enter different states as new data is input to the system over time
- What must be true for a state machine design to be valid?
- What are two important ways to represent a state machine?
- What is a possible disconnect between state machine design and physical implementation?
- What is the rate of growth of a state machine's complexity as more bits are added to a binary system input sequence?
There are two ways that state machines are usually represented: graphs and transition tables. These are used for various purposes. The visualization of a graph is typical when human understanding is important. It gives a visual sense of what the system does at any point in time. Both graphs and tables are easily represented in a computer program. So, their analysis and manipulation are readily automated.
At a minimum, a state machine specification must have the following for the specification to be valid. This is not just a theoretical curiosity. There are many implications for practical application:
- An initial state.
- A separate state for each step of the proper data sequence received from the system input.
- The ability to handle all possible system input data sequences, including those unexpected.
- Mutual Exclusivity: Only one transition from a state can be had for any system input.
- Collective Exhaustivity: Each state must specify what is to be done with ALL possible system inputs.
There is often a disconnect between theory and reality, and between design "on paper" and implementation in reality. For example, let us assume that we are using binary numbers to represent system input data sequences. The digits (bits) making up the number get set according to what the system generates as input. That is the mathematical theory, numbers written in binary, numbers in Base 2, N2 instead of N10. The binary number is called a "word" in digital electronics.
Digital electronics standardizes on certain word sizes (number of bits in a binary number). One finds word sizes in 4, 8, 16, 32, and 64 bits. Custom word sizes can be constructed but that is a lot more expensive. Most design-to-implementation uses standard word sizes. Let's do just that. Now, assume the state machine we want to implement uses only three bits. It is great to optimize a state machine design since that can lead to lower implementation cost. But, the smallest four-bits is the smallest word size we can purchase from standard components, and we want to stick to standard components. So, all our memory, and words will be four-bit oriented. Data flow will be four, not three, bits. Memory will be four bits. Memory addresses will be able to access ALL memory, not just that addressable by three bits. Be sure to accommodate memory address errors from unexpected words being generated as system input. Also be sure state transitions account for those too.
When just considering binary words, the complexity of a state machine can increase rapidly as a larger range of possible system inputs become possible. Just adding one bit to a word causes the system data input potential to double. Be aware of that and be careful to fully accommodate all possibilities.
Review State Transition Diagrams.
Unit 9 Vocabulary
This vocabulary list includes terms you will need to know to successfully complete the final exam.
- abstract machine
- discrete-state system
- finite automaton
- finite-state automaton (FSA)
- finite-state machine (FSM)
- initial state
- Mealy machines
- Moore machines
- state machine
- state transitions
- transition tables