Finite State Machines as Models of Physical System Equivalence Machines

Definition

A finite state machine is a formal model consisting of a finite set of states, an input alphabet, a transition function, a start state, and optionally a set of accepting or output states. In the context of physical system equivalence machines, the states represent equivalence classes of physically distinguishable situations that behave the same way for all relevant future inputs.

More formally, two physical system conditions are considered equivalent if, for every possible future input sequence, they produce the same observable behavior or lead to the same logical outcome. An FSM models this by placing those conditions into the same state.

General FSM form:

Q

= finite set of states

Σ

= set of inputs

δ

= transition function, δ(q, a) → q'

q₀

= initial state

F

= set of final/accepting states (if needed)

In physical system modeling, the FSM can be:

Deterministic

, where each input causes exactly one next state

Non-deterministic

, where an input may lead to more than one possible next state, though physical models usually prefer deterministic behavior for predictability

Main Content

1. Equivalence of Physical States

Equivalent physical states

are conditions of a system that cannot be distinguished by any future input-output behavior relevant to the model.
Instead of tracking every microscopic detail, FSMs group these conditions into a smaller number of abstract states, making the model simpler and more useful.

In physical systems, not every difference matters. For example:

A room thermostat may not care whether the temperature is 24.1°C or 24.2°C if both are treated as “comfortable.”
A traffic light controller may not care about the exact internal circuit voltage as long as the light remains in the same operational state.

This idea is called state equivalence. Two states are equivalent if:

They produce the same output for the same input
They transition to equivalent states under the same input
They cannot be distinguished by any sequence of future inputs

Example: A vending machine may have separate physical configurations due to internal mechanical positions, but if two configurations both mean “waiting for coin,” they can be modeled as one equivalent state.

Why this matters:

Reduces complexity
Improves understanding of system behavior
Helps in minimization of machines
Avoids unnecessary detail in design

2. Modeling Physical Systems with Finite States

Many physical systems naturally operate in distinct modes, such as ON/OFF, OPEN/CLOSED, IDLE/ACTIVE, or LOCKED/UNLOCKED.
FSMs represent these modes as states, and events such as button presses, sensor signals, or timeouts as inputs that cause transitions.

Physical systems often have a finite number of meaningful operating conditions. FSMs are suitable when:

The system’s behavior depends on current mode and input
The future behavior can be predicted from the current state
The system can be divided into discrete conditions

Common physical examples:

Thermostat

heating, cooling, idle

Elevator

moving up, moving down, stopped, door open

Washing machine

fill, wash, rinse, spin, done

Traffic signal

red, yellow, green

Security door system

locked, unlocked, alarmed

ASCII representation for a simple traffic light FSM:

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

Here each bracketed item is a state, and the timer acts as the input causing transitions.

Benefits of this modeling approach:

Easier to design control logic
Easier to test physical behavior
Helps convert real-world operation into formal logic
Supports implementation in digital circuits and controllers

3. Equivalence Machines and State Minimization

An equivalence machine is one in which states are partitioned into equivalence classes so that each class represents one behaviorally identical group.
State minimization removes redundant states while preserving the same external behavior.

In propositional logic and FSM theory, minimization is important because:

It creates the smallest possible machine that performs the same function
It removes duplicated or unnecessary states
It makes hardware and software implementations more efficient

How equivalence is determined: Two states are equivalent if:

They produce the same outputs for all inputs
Their next states are also equivalent for the same inputs

This recursive criterion is the basis of machine equivalence.

Example: Suppose a door controller has states:

S1 = locked and idle
S2 = locked but waiting If both states respond identically to every possible input, they can be merged into one state.

Practical significance in physical systems:

Lower circuit size
Fewer control signals
Reduced power consumption
Simpler maintenance and verification

Conceptual partitioning example:

Physical situations:
A, B, C, D

Equivalence classes:
{A, B} -> State 1
{C}    -> State 2
{D}    -> State 3

This means A and B are treated as equivalent in the machine model.

Working / Process

1. Identify the physical system and its relevant behaviors

Determine what aspects of the system matter for the model.
Ignore details that do not affect future behavior.
Example: In a fan controller, “speed 1” and “speed 1.0” may be treated the same if the controller cannot distinguish them.

2. Define the states as equivalence classes

Group all physically equivalent situations into one state.
Each state should represent a unique observable behavior pattern.
Example: A thermostat may have states such as heating, idle, and cooling.

3. Specify inputs, outputs, and transitions

Inputs may include sensor readings, user actions, timers, or external events.
The transition function defines how the machine moves from one state to another.
If outputs are included, ensure equivalent states give identical outputs for all inputs.

Example process for a simple door alarm system:

State 1: Closed and secure
State 2: Open
State 3: Alarm triggered

Inputs: open button, close button, intruder detected, reset
Transitions:
Closed and secure --open button--> Open
Open --close button--> Closed and secure
Open --intruder detected--> Alarm triggered
Alarm triggered --reset--> Closed and secure

This shows how physical actions correspond to state changes.

Advantages / Applications

Simplifies complex physical systems

FSMs reduce real-world complexity by focusing only on behaviorally relevant states.
This makes analysis and design manageable.

Useful in automatic control and embedded systems

Many controllers in appliances, vehicles, and industrial machines are FSM-based.
They provide predictable responses to inputs.

Helps in verification and optimization

FSMs allow checking whether a system behaves correctly under all possible inputs.
Equivalent states can be merged to minimize hardware/software resources.

Additional applications include:

Digital circuit design
Robotics control
Communication protocols
Traffic management systems
Vending machines
Elevator control
Microcontroller-based automation

Why FSMs are ideal for physical system equivalence machines:

They model discrete, observable modes
They support formal reasoning using logic
They make equivalent behavior explicit
They can be implemented directly in hardware and software

Summary

Finite state machines model physical systems by representing their meaningful operating conditions as states.
Equivalence machines group physically indistinguishable situations into the same state to simplify behavior analysis.
FSMs are widely used in control systems because they are simple, precise, and efficient.

Finite state machines are therefore a powerful way to represent and study physical systems whose behavior can be captured by a limited number of equivalent states and transitions.