A finite-state machine (FSM) is a mathematical model of computation. It is an abstract machine that can only be in one of several finite states at any given time. Thus, a finite-state machine is not a mechanical machine. It is not even an electric machine. Instead, it is a concept that we can use to solve various automation problems.

As the name implies, the finite-state machine has a fixed number of states. "A state is a description of the status of a system that is waiting to execute a transition. A transition is a set of actions to be executed when a condition is fulfilled or when an event is received." (from Wikipedia) 

There are two types of FSMs, namely Mealy and Moore. These are conceptually very similar but have small differences in how they are implemented. Moore machines assign output values to each state, with each transition being induced by inputs. Mealy machines, on the other hand, do not assign outputs to each state; instead, transitions generate outputs. To have a uniform format for class examples, projects, and homework assignments, we use Mealy machines in this course. 

A formal description of a FSM is as follows:

• A finite number k of discrete states, {S1,...,Sk}, one of which is designated as the initial state Si;

• A finite number m of digital inputs {I1,...,Im};

• A finite number n of digital outputs {O1,...,On};

• A set of transition rules specifying a next state s′(s,I1,...,Im) for each state s and set of inputs I1,...,Im;

• A set of output rules specifying output values O1(s,I1,...,Im),...,On(s,I1,...,Im) for each state s and set of inputs I1,...,Im

Altough the formal description might seem intimidating, in practice, FSMs are relatively easy to build. In the next page, we use a detailed example to learn what an FSM is.