Finite-State Machine

/ˈfaɪnɪt steɪt məˌʃiːn/

noun … “Model of computation with a limited number of states.”

Finite-State Machine (FSM) is an abstract computational model used to design sequential circuits or software systems. It consists of a finite set of states, a set of inputs that trigger transitions between states, and a set of outputs determined by its current state (and sometimes input). FSMs are widely used for modeling control logic, communication protocols, parsers, and embedded systems.

Key characteristics of Finite-State Machine include:

• Finite number of states: the system can only be in one state at a time.
• State transitions: movement between states triggered by input events.
• Deterministic or nondeterministic: deterministic FSMs have exactly one next state per input, while nondeterministic FSMs can have multiple possibilities.
• Outputs: determined either solely by state (Moore machine) or by state and input (Mealy machine).
• Applications: control systems, protocol design, sequence detection, UI navigation, and parser design.

Workflow example: Simple traffic light controller:

states = ["Green", "Yellow", "Red"]
current_state = "Green"

def transition(input_event):
    if current_state == "Green" && input_event == "timer":
        return "Yellow"
    elif current_state == "Yellow" && input_event == "timer":
        return "Red"
    elif current_state == "Red" && input_event == "timer":
        return "Green"
    return current_state

current_state = transition("timer")

Here, the traffic light cycles through a fixed set of states based on input events, illustrating a deterministic FSM.

Conceptually, a Finite-State Machine is like a board game with defined spaces: the player moves from one state to another according to the rules triggered by dice rolls or cards.

See Sequential Circuit, Flip-Flop, Digital, Control Logic, State Transition.