---
id: 20251223170627
title: Finite State Machines
type: permanent
created: 2025-12-23T22:06:27Z
modified: 2025-12-23T22:39:00Z
tags: []
---

# Finite State Machines

Finite State Machines are a computer science term for
machines that have a finite number of states, with clearly
defined transitions between them. Sometimes, FSM are
referred to simply as *state machines*. 

FSM are an abstraction of a computational system. FSM are
heavily used in systems that have clearly defined discrete
states. Examples include traffic lights, elevators,
combination locks, or others.

FSM have **actions**. Actions are the unabstractified
version of whatever the execution is. For physical systems,
it might be something like turning a motor on.

FSM can be categorized into two main categories:

## Acceptors (or 'detectors' or 'recognizers') Acceptors are
a type of FSM that produce binary output, recognizing
whether or not a given input is accepted. Examples of
systems that are acceptors include things like ready-commit
systems, or a password checker. These systems have an input,
and reach a state that determines the input is acceptable,
or incorrect. 

## Transducers
Transducers are a set of finite state machines that produce
an output based on input or state using *actions*. Actions
in this case represent a transition between state that
also has some external change. A finite state machine of an
elevator would have actions of the elevator changing between
floors, for example.

Transducers with respect to control have two different
types:
[[mealy-machines]] -- these have output depend on state and input
[[moore-machines]] -- these have output depend on state ONLY