Unit 9: Finite-State Automata
A finite-state machine (FSM) is a mathematical model of computation that describes an abstract machine in 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, or 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.
Completing this unit should take you approximately 2 hours.
Upon successful completion of this unit, you will be able to:
- illustrate abstract machines that can be in exactly one of a finite number of states at any given time;
- analyze systems that recognize input patterns, accepting or rejecting an input depending on whether a given pattern occurs;
- construct discrete-state systems; and
- predict how a given system will enter different states as new data is input to the system over time.
Read this article for a quick look at finite state machines.
This short video explains further.
Read this section to go into more detail on FSMs.
9.2: State Transition Diagrams
How we illustrate a finite-state machine has a great deal to do with how well others will understand our design. There is also an opportunity for objective review and evolution of the underlying system. This video continues with a discussion on the design of a combination lock.
9.3: Finite-State Machine States
This short video explains more about states in a finite-state machine.
Review these example designs of relatively simple practical applications of finite-state machines.
9.4: Putting the Basics to Use
Watch these videos for examples of using FSMs in the real world. They also discuss some subtle issues related to implementing FSMs.
Unit 9 Assessment
- Receive a grade
Take this assessment to see how well you understood this unit.
- This assessment does not count towards your grade. It is just for practice!
- You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
- You can take this assessment as many times as you want, whenever you want.