Back to course 'CS202: Discrete Structures'

Topic outline

  • Unit 9: Finite-State Automata

    Collapse all Expand all

    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

      • page icon
        Finite-State Machine Overview Page
        Students must
        Mark as done

        Read this article for a quick look at finite state machines.

      • page icon
        More on Finite State Machines Page
        Students must
        Mark as done

        This short video explains further.

      • page icon
        State Machines Page
        Students must
        Mark as done

        Read this section to go into more detail on FSMs.

    • 9.2: State Transition Diagrams

      • page icon
        State Transition Diagrams Page
        Students must
        Mark as done

        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

      • page icon
        FSM States Page
        Students must
        Mark as done

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

      • page icon
        FSM Examples Page
        Students must
        Mark as done

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

    • 9.4: Putting the Basics to Use

    • Unit 9 Assessment

      • quiz icon
        Unit 9 Assessment Quiz
        Students must
        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.