• 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.

    • 9.1: Introduction

    • 9.2: State Transition Diagrams

      • State Transition Diagrams Page

        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

      • FSM States Page

        This short video explains more about states in a finite-state machine.

      • FSM Examples Page

        Review these example designs of relatively simple practical applications of finite-state machines.

    • 9.4: Putting the Basics to Use

      • Putting the Basics to Use Page

        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

      • Unit 9 Assessment Quiz
        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.