The Central Idea
A finite-state machine, or FSM, is a mathematical model of a system with:
- a finite collection of states;
- a collection of possible inputs;
- rules that determine how inputs change the current state;
- often, a collection of outputs associated with states or transitions.
At any moment, the system is in exactly one current state.
Why State Matters
A combinational circuit depends only on its present inputs.
A finite-state machine depends on:
\[ \boxed{\text{current state}+\text{current input}}. \]The current state summarizes relevant information about the past.
A Simple Example: A Turnstile
Consider a turnstile with two states:
\[ L=\text{locked}, \] \[ U=\text{unlocked}. \]Suppose the inputs are:
\[ c=\text{coin inserted}, \] \[ p=\text{person pushes}. \]The current state determines how the same input should be interpreted.
Turnstile Transition Rules
A simple turnstile might follow these rules:
- if locked and a coin is inserted, become unlocked;
- if unlocked and pushed, become locked;
- if locked and pushed, remain locked;
- if unlocked and another coin is inserted, remain unlocked.
These rules define the machine's state transitions.
State
A state is a condition of the system that summarizes the information needed to determine future behavior.
States should contain enough information to distinguish different future responses.
They should not contain irrelevant history.
Finite State Set
An FSM has only finitely many states.
If the state set is
\[ Q=\{q_0,q_1,q_2,q_3\}, \]then the machine has four possible states.
The notation \(Q\) is commonly used for the state set.
Input Alphabet
The set of possible input symbols is often called the input alphabet.
It is commonly written
\[ \Sigma. \]For a binary-input system,
\[ \Sigma=\{0,1\}. \]Transition Function
The rule that determines the next state is called the transition function.
For a deterministic finite-state machine, it can be written
\[ \delta:Q\times\Sigma\to Q. \]This means that a current state and an input symbol determine exactly one next state.
Reading the Transition Function
If
\[ \delta(q_1,0)=q_2, \]then:
- the current state is \(q_1\);
- the current input is \(0\);
- the next state is \(q_2\).
Initial State
A finite-state machine usually specifies an initial state.
It is often written
\[ q_0. \]The initial state tells us where the machine begins before any input is processed.
State Diagrams
A state diagram represents states as nodes and transitions as directed arrows.
Each arrow is labeled with the input that causes the transition.
A loop from a state back to itself represents an input that leaves the state unchanged.
Transition Tables
A transition table gives the same information in tabular form.
For example:
| Current State | Input 0 | Input 1 |
|---|---|---|
| \(q_0\) | \(q_0\) | \(q_1\) |
| \(q_1\) | \(q_0\) | \(q_1\) |
State Diagram and Transition Table Are Equivalent
A state diagram emphasizes visual flow.
A transition table emphasizes systematic lookup.
Both describe the same transition function.
Processing an Input String
Suppose an FSM begins in
\[ q_0 \]and receives the input string
\[ 1011. \]The machine processes one symbol at a time.
Each input updates the current state, and the resulting state becomes the starting state for the next input symbol.
State Sequence
The sequence of states visited while processing an input is called the machine's state sequence or run.
For example,
\[ q_0\to q_1\to q_1\to q_0\to q_1 \]records a five-state run produced by four input symbols.
Example: Remember the Last Bit
Consider a machine whose state records the most recently read binary digit.
Use states
\[ Z=\text{last bit was }0 \]and
\[ O=\text{last bit was }1. \]Reading \(0\) moves to \(Z\).
Reading \(1\) moves to \(O\).
Transition Table for Last-Bit Memory
| Current State | Input 0 | Input 1 |
|---|---|---|
| \(Z\) | \(Z\) | \(O\) |
| \(O\) | \(Z\) | \(O\) |
The next state depends only on the new bit because the machine's purpose is to remember that newest bit.
State as Compressed History
An FSM does not usually remember the entire sequence of past inputs.
Instead, the current state stores only the information from the past that is relevant to future behavior.
This is one of the most important ideas in finite-state modeling.
Example: Even or Odd Number of 1s
Consider a machine that tracks whether the number of \(1\)s seen so far is even or odd.
Use states
\[ E=\text{even number of 1s} \]and
\[ O=\text{odd number of 1s}. \]Reading a \(0\) leaves the parity unchanged.
Reading a \(1\) switches between \(E\) and \(O\).
Parity Transition Table
| Current State | Input 0 | Input 1 |
|---|---|---|
| \(E\) | \(E\) | \(O\) |
| \(O\) | \(O\) | \(E\) |
Processing a Parity Example
Begin in \(E\), meaning zero \(1\)s have been seen.
Process
\[ 10110. \]The state sequence is
\[ E \xrightarrow{1} O \xrightarrow{0} O \xrightarrow{1} E \xrightarrow{1} O \xrightarrow{0} O. \]The final state is \(O\), so the string contains an odd number of \(1\)s.
Outputs
Some finite-state machines only track state transitions.
Others also produce outputs.
The output may depend on:
- the current state;
- the current transition;
- both the current state and current input.
Moore Machines
In a Moore machine, the output depends only on the current state.
Formally, an output function can be written
\[ \lambda:Q\to\Gamma, \]where \(\Gamma\) is the output alphabet.
Example of Moore Output
Suppose a traffic controller has states:
\[ R=\text{red}, \qquad G=\text{green}, \qquad Y=\text{yellow}. \]The visible light is determined directly by the current state.
This is naturally modeled as a Moore-style output.
Mealy Machines
In a Mealy machine, the output depends on the current state and the current input.
The output function can be written
\[ \lambda:Q\times\Sigma\to\Gamma. \]Outputs are therefore naturally associated with transitions.
Moore versus Mealy
A Moore machine associates outputs with states.
A Mealy machine associates outputs with state-input combinations.
The two models can often describe equivalent overall behaviors, but their state structures may differ.
Deterministic Behavior
A finite-state machine is deterministic when each current-state/input pair has exactly one next state.
Formally,
\[ \delta(q,a) \]must produce one unique state for every allowed \(q\) and \(a\).
Incomplete Transition Rules
If a deterministic model is intended to process every possible input, then every state must have a defined transition for every input symbol.
A missing transition means the machine description is incomplete unless the model explicitly allows termination or rejection at that point.
Self-Loops
A transition may return to the same state:
\[ \delta(q,a)=q. \]This is represented by a loop in a state diagram.
A self-loop means that the input is processed without changing the stored state.
Reachable States
A state is reachable if some input sequence can move the machine from the initial state to that state.
A state that can never be reached has no effect on the machine's behavior from its designated start.
Unreachable States
Suppose
\[ Q=\{q_0,q_1,q_2\} \]but every transition from \(q_0\) and \(q_1\) stays within
\[ \{q_0,q_1\}. \]If no transition enters \(q_2\), then \(q_2\) is unreachable from \(q_0\).
Equivalent States
Two states may be behaviorally equivalent if no future input sequence can distinguish them with respect to the machine's outputs or acceptance behavior.
Equivalent states can sometimes be merged.
This leads to state minimization.
State Minimization
State minimization seeks a smaller machine with the same observable behavior.
Typical simplifications include:
- removing unreachable states;
- merging equivalent states.
The goal is not merely fewer labels but fewer behaviorally distinct states.
Finite-State Machines and Memory
The current state acts as a finite memory register.
A machine with \(k\) states can remember one of \(k\) possible abstract situations.
It cannot store an arbitrary amount of unbounded information unless the model is extended.
Encoding States with Bits
Digital implementations often encode FSM states with binary values.
If a machine has four states, two bits are sufficient because
\[ 2^2=4. \]If it has five through eight states, at least three bits are needed because
\[ 2^2<5\le 2^3. \]Minimum Bits for State Encoding
To encode \(n\) distinct states using binary storage, the minimum number of bits \(b\) satisfies
\[ 2^b\ge n. \]Equivalently,
\[ \boxed{b=\lceil\log_2 n\rceil}. \]Next-State Logic
In a digital FSM, Boolean logic can compute the next encoded state from:
\[ \text{current state bits} \]and
\[ \text{current input bits}. \]Thus finite-state machines combine Boolean combinational logic with stored state.
Current State and Next State
It is important to distinguish:
\[ \text{current state} \]from
\[ \text{next state}. \]The transition function computes the next state, which becomes the new current state after the transition occurs.
Example: Two-State Toggle Machine
Consider two states
\[ A,\qquad B. \]Let input \(0\) leave the current state unchanged and input \(1\) switch states.
| Current State | Input 0 | Input 1 |
|---|---|---|
| \(A\) | \(A\) | \(B\) |
| \(B\) | \(B\) | \(A\) |
Processing the Toggle Machine
Begin in \(A\) and process
\[ 10101. \]The run is
\[ A \xrightarrow{1} B \xrightarrow{0} B \xrightarrow{1} A \xrightarrow{0} A \xrightarrow{1} B. \]The final state is
\[ \boxed{B}. \]Sequence Detection
An FSM can detect whether a recent input pattern has occurred.
For example, a machine designed to detect
\[ 101 \]may use states representing how much of the target pattern has already been matched.
States as Partial Progress
For the pattern \(101\), useful states might be:
- \(q_0\): no useful prefix matched;
- \(q_1\): the suffix currently matches \(1\);
- \(q_2\): the suffix currently matches \(10\);
- \(q_3\): the pattern \(101\) has been detected.
Each state compresses the relevant part of the input history.
State Design Requires the Right Memory
A useful state must remember enough information to determine the correct future transition.
If two past histories can lead to different future behavior, they cannot be represented by the same state.
Too Few States
A model with too few states may merge situations that require different future responses.
The resulting machine will then produce incorrect transitions or outputs.
Too Many States
A model with too many states may distinguish histories that have no effect on future behavior.
Such a machine may still be correct, but it is unnecessarily complex.
Example: Vending Machine
Suppose an item costs 25 cents and the machine accepts nickels and dimes.
States can represent the amount currently credited:
\[ 0,\ 5,\ 10,\ 15,\ 20. \]Inputs change the credit state until enough value has been inserted to dispense the item.
Why a Vending Machine Is Naturally Stateful
The effect of inserting a dime depends on how much credit is already stored.
A dime inserted at 0 cents does not produce the same next state as a dime inserted at 15 cents.
The current state therefore stores essential information about previous inputs.
Example: Traffic Signal Controller
A simplified traffic controller may cycle through
\[ G\to Y\to R\to G. \]Timer events or sensor inputs trigger transitions.
The current state determines the currently displayed signal.
Example: Door Controller
An automatic door might have states such as:
- closed;
- opening;
- open;
- closing.
Inputs from sensors and timers determine the transitions.
Example: Communication Protocol
A communication system can use states such as:
- idle;
- waiting for acknowledgment;
- retrying;
- completed.
Messages and timeout events serve as inputs.
Finite-State Machines in Software
FSMs are common in software systems that move through a controlled collection of modes.
Examples include:
- user-interface workflows;
- network protocols;
- game character behavior;
- parsers;
- device controllers;
- business process workflows.
Finite-State Machines and Formal Languages
A finite-state machine can process a string of symbols one symbol at a time.
By designating some states as accepting, the machine can classify strings according to whether their final state satisfies a condition.
This perspective leads directly to automata and formal languages.
Accepting States
In an acceptor-style finite-state machine, some states are designated accepting states.
If processing an entire input string ends in an accepting state, the string is accepted.
Otherwise, it is rejected.
Example: Accept Strings Ending in 1
Use two states:
\[ Z=\text{last symbol is }0 \]and
\[ O=\text{last symbol is }1. \]Designate \(O\) as accepting.
Then any nonempty binary string ending in \(1\) finishes in \(O\) and is accepted.
Finite-State Machines Are Discrete Dynamical Systems
An FSM evolves in discrete steps.
At each step:
- the machine has a current state;
- an input is received;
- the transition rule is applied;
- a next state is produced.
This makes finite-state machines a basic form of discrete dynamical system.
Common Error: Ignoring the Current State
In a finite-state machine, the same input can produce different next states depending on the current state.
The input alone does not determine the transition.
Common Error: Treating State as the Entire History
State should summarize only the history needed for future behavior.
Recording every previous input would usually defeat the purpose of a finite state model.
Common Error: Omitting a Transition
In a complete deterministic machine, every state/input pair must specify one next state.
Missing entries make the transition function incomplete.
Common Error: Giving Two Next States for One Input
In a deterministic FSM,
\[ \delta(q,a) \]must have exactly one value.
Assigning two different next states to the same state/input pair violates determinism.
Common Error: Confusing Output with Next State
The next state tells where the machine moves.
The output tells what the machine reports or does.
They may be related, but they are not the same object.
Common Error: Confusing Moore and Mealy Output
In a Moore machine, output depends on the state.
In a Mealy machine, output depends on the state and current input.
Keeping that distinction clear prevents incorrect output labeling.
Common Error: Counting Unreachable States as Necessary
A state that cannot be reached from the initial state contributes nothing to the actual behavior of the machine from that start.
Removing unreachable states is often the first step in simplification.
A Reliable Procedure for Reading a Transition Table
- Identify the current state.
- Read the next input symbol.
- Locate the corresponding table entry.
- Move to the listed next state.
- Repeat for the remaining input symbols.
- Record any output required by the model.
A Reliable Procedure for Building a State Diagram
- List all states.
- Draw one node for each state.
- Mark the initial state.
- For each state and each possible input, determine the next state.
- Draw a directed arrow to that next state.
- Label the arrow with the triggering input.
- Add outputs according to the chosen machine model.
A Reliable Procedure for Designing States
- Identify what future decisions the machine must make.
- Determine what information from the past affects those decisions.
- Create states that represent distinct relevant memories.
- Merge histories that lead to identical future behavior.
- Separate histories that require different future behavior.
- Define transitions for every allowed input.
- Test the machine with representative input sequences.
Example: Full Processing Workflow
Use the parity machine with states \(E\) and \(O\):
| Current State | Input 0 | Input 1 |
|---|---|---|
| \(E\) | \(E\) | \(O\) |
| \(O\) | \(O\) | \(E\) |
Begin in \(E\) and process
\[ 1101. \]Step 1:
\[ E\xrightarrow{1}O. \]Step 2:
\[ O\xrightarrow{1}E. \]Step 3:
\[ E\xrightarrow{0}E. \]Step 4:
\[ E\xrightarrow{1}O. \]Therefore, the final state is
\[ \boxed{O}. \]Practice 1: Identify the State Concept
In a turnstile with states locked and unlocked, what does the state represent?
Practice 2: Read a Transition
If
\[ \delta(q_2,1)=q_3, \]what happens when the machine is in \(q_2\) and receives input \(1\)?
Practice 3: Count State Bits
What is the minimum number of binary bits needed to encode \(6\) states?
Practice 4: Toggle Machine
A machine starts in \(A\). Input \(0\) leaves the state unchanged, and input \(1\) switches between \(A\) and \(B\).
What is the final state after
\[ 1110? \]Practice 5: Parity Machine
Starting in the even state \(E\), what is the final state after processing
\[ 10101? \]Practice 6: Moore or Mealy?
A machine's output depends only on its current state.
Is it Moore-style or Mealy-style?
Practice 7: Self-Loop
What does
\[ \delta(q,0)=q \]mean?
Practice 8: Reachability
A state has no incoming path from the initial state.
What kind of state is it?
Practice 9: Current versus Next State
If the current state is \(q_1\) and
\[ \delta(q_1,a)=q_4, \]which state becomes current after input \(a\) is processed?
Practice 10: State Memory
Why can two different input histories sometimes lead to the same state?
Practice Answers
Practice 1
The state represents the turnstile's current operating condition: whether passage is currently blocked or permitted.
Practice 2
The machine moves from \(q_2\) to \(q_3\):
\[ \boxed{q_2\xrightarrow{1}q_3}. \]Practice 3
We need the smallest \(b\) such that
\[ 2^b\ge6. \]Since
\[ 2^2=4<6 \]and
\[ 2^3=8, \]the answer is
\[ \boxed{3\text{ bits}}. \]Practice 4
Start in \(A\):
\[ A\xrightarrow{1}B \xrightarrow{1}A \xrightarrow{1}B \xrightarrow{0}B. \]Therefore,
\[ \boxed{B}. \]Practice 5
The string \(10101\) contains three \(1\)s, which is odd.
Therefore, the final state is
\[ \boxed{O}. \]Practice 6
\[ \boxed{\text{Moore machine}}. \]Practice 7
Input \(0\) leaves the machine in the same state.
This is a
\[ \boxed{\text{self-loop}}. \]Practice 8
It is
\[ \boxed{\text{unreachable}}. \]Practice 9
After input \(a\) is processed,
\[ \boxed{q_4} \]becomes the current state.
Practice 10
Different histories can lead to the same state when the differences between those histories no longer matter for future behavior.
The state stores only the relevant information from the past.
What to Remember
- A finite-state machine has finitely many states and transition rules.
- The current state summarizes the relevant past.
- The next state depends on the current state and current input.
- A deterministic FSM has exactly one next state for each state/input pair.
- State diagrams and transition tables represent the same transition structure.
- Moore outputs depend on state; Mealy outputs depend on state and input.
- Unreachable states can often be removed.
- Equivalent states can sometimes be merged.
- Binary state encoding requires \(\lceil\log_2 n\rceil\) bits for \(n\) states.
- FSMs connect Boolean logic with stored memory and sequential behavior.
The central habit is to ask what information from the past must be remembered so that the next response can be determined correctly.
Where We Go Next
Finite-state machines model systems that process inputs while moving among a finite collection of states. When these machines are used to recognize strings and languages, they become central objects in automata theory.
The next lesson, Automata, develops finite automata as formal recognizers and introduces acceptance, deterministic and nondeterministic models, and the connection between machines and languages.