A finite state machine (FSM) is a mathematical model of computation that processes inputs by transitioning between discrete states. It consists of states, transitions, and actions, operating under strict rules.
An FSM begins in an initial state. When it receives input, it follows predefined rules to transition to another state. These transitions can trigger actions, such as outputting data or changing system behavior. The machine continues processing inputs until it reaches a final state or halts.
| Type | Description | Example Use Case |
|---|---|---|
| Deterministic Finite Automaton (DFA) | Each state transition is uniquely determined by the current state and input symbol. | Text pattern matching (e.g., checking if a string contains "cat"). |
| Non-Deterministic Finite Automaton (NFA) | From a given state, multiple transitions may occur for the same input symbol. | Regular expression parsing. |
| Mealy Machine | Outputs depend on both the current state and input symbol. | Combinational logic circuits. |
| Moore Machine | Outputs depend solely on the current state. | Sequential logic circuits. |
FSMs are widely used in computer science, electrical engineering, and linguistics. They model systems with simple, predictable behaviors, such as vending machines, traffic lights, and syntax analyzers. Their efficiency and ease of implementation make them ideal for embedded systems and protocol design.
For example, a vending machine FSM might have states like "Idle," "Waiting for Input," and "Dispensing Product." Transitions occur when a user selects an option or inserts money, leading to actions like dispensing a product or returning change.
Many people confuse FSOs with more complex models like Turing machines. Unlike Turing machines, FSOs cannot handle unbounded memory or perform arbitrary computations. They are limited to problems solvable with regular expressions.
Another misconception is that FSOs are always deterministic. While DFAs are deterministic, NFAs introduce non-determinism, allowing multiple transitions from a single state. This capability makes NFAs more flexible in certain scenarios, though they can always be converted to equivalent DFAs.
I once built a simple FSM to control an LED's blinking pattern based on button presses. The FSM had three states: "Off," "Blinking Slowly," and "Blinking Rapidly." Each button press triggered a transition, demonstrating how FSOs can manage real-world interactions efficiently.
FSMs are foundational in computer science education and practical applications. They appear in compiler design, network protocols, and even game AI. Understanding FSOs provides insights into how systems process sequential inputs and make decisions based on their current state.
According to the Wikipedia entry on finite state machines, FSOs were first introduced by McCulloch and Pitts in 1943 as a model of neural networks. Their simplicity and versatility have made them a staple in theoretical computer science and practical engineering.