Introduction to Finite State Machine

Definition

A finite state machine is a system of computation consisting of a finite set of states, a set of input symbols, a transition function that determines how the machine moves between states, a starting state, and one or more accepting or final states.

In simple terms, an FSM is a model that:

is always in one state at a time,
changes state when it receives an input,
follows predefined rules for transitions,
and may produce output depending on the current state and input.

Formal definition

An FSM is commonly represented as a 5-tuple:

M = (Q, Σ, δ, q₀, F)

where:

Q

= finite set of states

Σ

= finite input alphabet

δ

= transition function, where δ: Q × Σ → Q

q₀

= initial state

F

= set of final or accepting states

Example

Consider a simple turnstile:

Locked

Unlocked

If the turnstile is locked and a coin is inserted, it moves to unlocked. If it is unlocked and a person pushes through, it returns to locked.

This system has a small number of states and clear transition rules, which makes it a perfect example of a finite state machine.

Main Content

1. States and State Transitions

A state is a specific condition or mode in which a system exists at a particular time. In an FSM, the entire behavior of the machine depends on its current state.
A state transition is the movement from one state to another when an input or event occurs. Transitions are defined by rules and are usually represented using arrows in a state diagram.

A finite state machine works because it does not need to remember every past event in detail. Instead, it only needs to know its current state. This makes FSMs efficient and easy to analyze.

Example: Traffic Light Controller

A traffic light can be modeled with three states:

Red
Green
Yellow

The transitions occur in a fixed order:

Red → Green
Green → Yellow
Yellow → Red

ASCII state diagram for a traffic light system

[Red] --timer--> [Green] --timer--> [Yellow] --timer--> [Red]

This shows that the system changes state only when the timing condition is satisfied.

Why states matter

They simplify complex behavior into manageable units.
They help design systems that respond predictably.
They are useful in both hardware and software implementation.

2. Components of a Finite State Machine

Finite set of states (Q)

These are all possible conditions of the machine. Since the set is finite, the machine cannot have unlimited memory.

Input alphabet (Σ)

This is the set of all possible inputs that the machine can receive. For example, in a binary FSM, the input alphabet may be {0, 1}.

Other essential components include:

Transition function (δ)

Defines how the system changes from one state to another for a given input.

Initial state (q₀)

The state where processing begins.

Final/accepting states (F)

States that indicate successful completion or acceptance of an input string.

Example: Binary string ending in 1

Suppose we want an FSM that accepts binary strings ending in 1.

States:

q0

= start state

q1

= last input seen was 1

q2

= last input seen was 0

Transitions:

From q0, on input 1 → q1
From q0, on input 0 → q2
From q1, on input 0 → q2
From q1, on input 1 → q1
From q2, on input 0 → q2
From q2, on input 1 → q1

Accepting state:

q1, because strings ending in 1 should be accepted.

Conceptual meaning

The machine does not store the full string. It only remembers enough information to determine whether the last symbol was 1.

3. Types of Finite State Machines

DFA (Deterministic Finite Automaton)

For every state and input symbol, there is exactly one next state. It is deterministic because the next move is always uniquely determined.

NFA (Nondeterministic Finite Automaton)

For a state and input symbol, there may be multiple possible next states or even no next state. NFAs are conceptually flexible and are often used in theory and pattern matching.

Deterministic FSM

A DFA has:

one transition for each input symbol from each state,
no ambiguity,
simple execution logic.

Nondeterministic FSM

An NFA has:

possible multiple transitions for the same input,
no requirement of a unique next state,
theoretical importance because every NFA can be converted into an equivalent DFA.

Example comparison

If a machine reads a character:

A DFA knows exactly where to go next.
An NFA may have several possible paths and can accept if at least one path leads to an accepting state.

Why this distinction is important

DFA is simpler to implement in real systems.
NFA is useful for designing and describing patterns concisely.
Both recognize the same class of languages: regular languages.

Working / Process

1. Start in the initial state

The finite state machine begins in the predefined starting state, usually denoted as q₀.
This state represents the machine before any input is processed.
Example: In a vending machine model, the start state may represent “waiting for coin.”

2. Read the input symbol or event

The machine reads the next input from the input sequence.
Based on the current state and the input symbol, the transition function determines the next state.
Example: If a coin is inserted into a turnstile, the input causes a transition from locked to unlocked.

3. Move to the next state and continue

After processing the input, the machine updates its current state.
This process repeats for every input symbol until the input ends.
If the final state is an accepting state, the input is accepted; otherwise, it is rejected.

Example: Parity checker for even number of 1s

States:

Even

= even number of 1s seen so far

Odd

= odd number of 1s seen so far

Rules:

Reading 0 does not change parity.
Reading 1 toggles between Even and Odd.

ASCII state diagram

          1
   +----------------+
   |                v
[Even] ---------> [Odd]
   ^                |
   |                |
   +------ 1 -------+

For input 1011:

Start in Even
Read 1 → Odd
Read 0 → Odd
Read 1 → Even
Read 1 → Odd

Since the final state is Odd, the string is not accepted if the machine is designed to accept only even parity.

Advantages / Applications

Simple representation of complex behavior

FSMs break down system behavior into a limited number of states, making design and understanding easier.
They are especially useful for sequential systems where memory of previous steps matters only in a limited way.

Useful in digital electronics and software systems

FSMs are used in control units, sequence detectors, embedded systems, and protocol design.
They are also used in compilers for lexical analysis, user interfaces, and workflow automation.

Supports clear analysis and verification

Since the number of states is finite, FSM behavior can be tested and verified systematically.
This makes FSMs valuable in reliability-critical systems such as traffic control, network communication, and automated machines.

Common applications

Traffic light controllers

Elevator control systems

Vending machines

Digital circuit design

Lexical analyzers in compilers

Communication protocols

Text pattern matching

Game development logic

Robotics and automation

Example application: Vending machine

A vending machine may have states like:

Idle
Money inserted
Item selected
Dispensing item

Each action changes the state. FSM modeling ensures the machine behaves correctly in all possible situations.

Summary

A finite state machine is a model that changes between a limited number of states based on inputs.
It is defined by states, inputs, transitions, an initial state, and accepting states.
FSMs are widely used in computer science, electronics, and automation to model predictable system behavior.