Finite State Machine Formal Definitions

You will define the components of a Finite State Machine including states, transitions, inputs, and outputs using formal mathematical notation.

Finite State Machine Formal Definitions

In this lesson, you will learn how to represent a Finite State Machine (FSM) using precise mathematical notation to bridge the gap between abstract logic and physical circuit design.

While we have used flip-flops to build counters, more complex systems require a formal way to track "where" the system is and "how" it should react to the outside world. A Finite State Machine is defined as a 6-tuple $M = (Q, \Sigma, \Delta, \delta, \lambda, q_0)$ :

$Q$ : A finite set of states. These represent the "memory" of your system (e.g., $S_0, S_1, S_2$ ).
$\Sigma$ : A finite set of inputs. These are the external signals that trigger changes.
$\Delta$ : A finite set of outputs. The values generated by the machine based on its current state.
$\delta$ : The state transition function, defined as $\delta: Q \times \Sigma \to Q$ . This dictates which state you move to next, given your current state and an input.
$\lambda$ : The output function, defined as $\lambda: Q \times \Sigma \to \Delta$ (or sometimes just $Q \to \Delta$ for Moore machines). This determines what the machine "does" while in a specific state.
$q_0$ : The initial state, or the starting point when the system resets.

A Practical Example

Imagine a simple two-state lock. When in state LOCKED ( $S_0$ ), if you receive a KEY input, you transition to UNLOCKED ( $S_1$ ).

We define the transition as: δ(S0, KEY) = S1

If the input is NONE, the state remains the same: δ(S0, NONE) = S0

In your hardware, these formal definitions correspond directly to logic components: the States ( $Q$ ) are stored in registers (flip-flops), the Transition Function ( $\delta$ ) is implemented with combinatorial logic gates that feed the flip-flop inputs, and the Output Function ( $\lambda$ ) is combinatorial logic that reads the current flip-flop state to drive external pins. By mapping these, you can design any sequential circuit systematically.

Key Takeaway: An FSM is formally defined as a mathematical tuple that maps current states and inputs to next states and outputs, providing a rigorous blueprint for implementing complex sequential control logic.