Finite State Machine

A Finite State Machine (FSM) is a computational model used to design and analyze the behavior of systems. FSMs are characterized by a finite number of states, transitions between those states, and actions that result from those transitions.

Overview

A finite state machine consists of:

• A finite set of states.
• A finite set of inputs.
• A transition function that determines the next state for a given state and input.
• An initial state.
• (Optionally) a set of final or accepting states.

FSMs are widely used in computer science, engineering, linguistics, and other fields for modeling sequential logic and systems.

Types of Finite State Machines

Finite state machines can be classified into two main types:

• Deterministic Finite Automaton (DFA): For every state and input, there is exactly one transition to a next state.
• Non-Deterministic Finite Automaton (NFA): For some states and inputs, there can be multiple possible next states or transitions.

Both DFAs and NFAs are equivalent in expressive power but differ in their implementation and complexity.

Components

The main components of an FSM are:

• States: Represent distinct configurations or conditions of the system.
• Transitions: Define how the system moves from one state to another based on inputs.
• Inputs: External stimuli or events that trigger transitions.
• Outputs (Optional): Actions or signals produced as a result of state transitions.

Formal Definition

An FSM can be represented as a 5-tuple:

• Q: A finite set of states.
• Σ: A finite set of input symbols (alphabet).
• δ: The transition function (δ: Q × Σ → Q).
• q₀: The initial state (q₀ ∈ Q).
• F: The set of final or accepting states (F ⊆ Q).

Examples

Turnstile

A turnstile can be modeled as an FSM with two states:

• Locked: The turnstile is locked and requires a coin to unlock.
• Unlocked: The turnstile is unlocked and allows a person to pass.

State	Input	Next State	Output
Locked	Insert Coin	Unlocked	Unlocks
Locked	Push	Locked	None
Unlocked	Push	Locked	Locks
Unlocked	Insert Coin	Unlocked	None

Vending Machine

A vending machine is another example of an FSM. It processes coins and dispenses items when the correct amount is inserted.

Applications

Finite state machines are used in various domains, including:

• Designing digital circuits.
• Parsing and lexical analysis in compilers.
• Network protocols.
• Control systems and embedded systems.
• Game development for modeling NPC behavior.

Advantages

• Simple to design and understand.
• Easy to implement in hardware or software.
• Provides a clear visualization of system behavior.

Limitations

• Not suitable for modeling systems with infinite states.
• Can become complex and unwieldy for large systems.

See Also

• Deterministic Finite Automaton
• Non-Deterministic Finite Automaton
• State Transition Diagram
• Turing Machine