The Central Idea
A configuration is one complete description of a discrete system.
A state space is the set of all configurations considered possible under the model.
If a system has several components, one state can often be represented as a tuple:
\[ (x_1,x_2,\ldots,x_n). \]Each coordinate records one part of the full configuration.
Simple Example: One Switch
A switch can be
\[ \text{off} \]or
\[ \text{on}. \]The state space is
\[ S=\{\text{off},\text{on}\}. \]Thus
\[ |S|=2. \]Two Binary Components
Suppose two switches each have states
\[ \{0,1\}. \]A complete system state must specify both switch values:
\[ (0,0),\quad (0,1),\quad (1,0),\quad (1,1). \]Therefore the state space contains
\[ \boxed{4} \]configurations.
Cartesian Products Build State Spaces
If one component has state set \(A\) and another has state set \(B\), then the combined system has state space
\[ A\times B. \]Each state is an ordered pair
\[ (a,b) \]with
\[ a\in A \]and
\[ b\in B. \]More Than Two Components
If a system has component state sets
\[ S_1,S_2,\ldots,S_n, \]then the unconstrained configuration space is
\[ \boxed{ S_1\times S_2\times\cdots\times S_n }. \]A state is an \(n\)-tuple
\[ (s_1,s_2,\ldots,s_n). \]Counting Unconstrained Configurations
If
\[ |S_1|=m_1,\quad |S_2|=m_2,\quad\ldots,\quad |S_n|=m_n, \]then the total number of unconstrained configurations is
\[ \boxed{ m_1m_2\cdots m_n }. \]This follows from independent choices for each component.
Binary Configuration Spaces
If each of \(n\) components has two possible states, then every configuration can be represented by a binary string
\[ b_1b_2\cdots b_n. \]The number of possible configurations is
\[ \boxed{2^n}. \]Example: Four Binary Components
Four switches produce states such as
\[ 0000,\quad 0101,\quad 1110,\quad 1111. \]The total state count is
\[ 2^4=\boxed{16}. \]Configurations Are Ordered Descriptions
In a configuration tuple,
\[ (0,1,0) \]generally differs from
\[ (1,0,0). \]Even though both contain two zeros and one one, the active component occurs in a different position.
Position identifies which component has which value.
State Variables
A state variable records one component of a system state.
If
\[ s=(x,y,z), \]then \(x\), \(y\), and \(z\) may be state variables.
Together they must contain enough information to distinguish relevant system states.
Complete versus Partial Descriptions
A true state description must be complete relative to the model.
Suppose a machine is described by
\[ (\text{mode},\text{door},\text{power}). \]Recording only
\[ \text{power}=\text{on} \]gives partial information, not necessarily a complete state.
Choosing the Right State Variables
State variables should include enough information to predict or analyze the next relevant behavior of the system.
Too little information can merge genuinely different states.
Too much information can make the state space unnecessarily large.
State design is therefore part of model design.
Example: Position and Direction
Suppose a robot occupies one of three locations,
\[ \{A,B,C\}, \]and faces either
\[ \{\text{left},\text{right}\}. \]Its state space is
\[ \{A,B,C\}\times\{\text{left},\text{right}\}. \]Therefore it has
\[ 3\cdot2=\boxed{6} \]states.
Configuration Space versus State Space
The terms configuration space and state space are often used similarly in discrete settings.
A useful distinction is:
- configuration space emphasizes possible arrangements of components;
- state space emphasizes system conditions relevant to evolution or behavior.
In many finite models, the same set serves both roles.
Constraints Reduce the State Space
The Cartesian product gives all combinations of component values, but some combinations may be forbidden.
Suppose two switches cannot both be on.
Then
\[ (1,1) \]is invalid.
The allowed state space becomes
\[ \{(0,0),(0,1),(1,0)\}. \]Feasible States
A state satisfying all model constraints is a feasible state.
The feasible state space is therefore a subset of the unconstrained product:
\[ F\subseteq S_1\times\cdots\times S_n. \]Constraints define which combinations remain possible.
Forbidden States
A forbidden state is a mathematically describable configuration excluded by the rules of the model.
For example, a scheduling state may assign one person to two incompatible tasks at the same time.
Such a tuple may exist syntactically but fail feasibility constraints.
Possible versus Reachable States
A state may satisfy all static constraints yet still be unreachable from a particular starting condition.
Therefore we distinguish:
- possible states, allowed by the model;
- reachable states, attainable through allowed transitions.
Example: Reachability
Suppose
\[ S=\{A,B,C,D\} \]with transitions
\[ A\to B,\qquad B\to C. \]If the system starts at \(A\), then \(A\), \(B\), and \(C\) are reachable.
State \(D\) may belong to the state space but remain unreachable.
State-Transition Relation
Allowed transitions define a relation
\[ T\subseteq S\times S. \]If
\[ (s,t)\in T, \]then the system is allowed to move from state \(s\) to state \(t\).
This relation can be represented as a directed graph.
Deterministic State Spaces
If each state has exactly one next state under a fixed rule, then the transition relation is a function
\[ F:S\to S. \]Starting from \(s_0\), the system generates
\[ s_0,s_1,s_2,\ldots \]where
\[ s_{n+1}=F(s_n). \]Nondeterministic State Spaces
If a state may have several possible successors, the transition rule is not a single-valued function.
For example,
\[ A\to B \]and
\[ A\to C \]describe two possible next states.
The state system is then nondeterministic unless another rule selects among them.
State Graphs
A state graph uses:
- vertices for states;
- directed edges for allowed transitions.
State graphs allow reachability, cycles, dead ends, and recurrent behavior to be studied visually and algorithmically.
Paths Represent Histories
A path through a state graph represents one possible history of the system.
The path
\[ s_0\to s_1\to s_2\to s_3 \]corresponds to the state sequence
\[ s_0,s_1,s_2,s_3. \]A state is one condition; a path records evolution through several conditions.
Configuration versus Trajectory
A configuration describes one state.
A trajectory is an ordered sequence of states:
\[ s_0,s_1,s_2,\ldots \]Confusing these two objects is like confusing one photograph with an entire film.
Initial States
A process may specify one or more allowed starting states.
If the system begins in
\[ s_0, \]reachability is usually measured relative to that initial condition.
Different initial states can produce different reachable regions.
Terminal States
A terminal state has no allowed outgoing transition.
It may represent:
- completion;
- failure;
- game over;
- a dead end;
- a final decision.
Absorbing States
An absorbing state is a state that, once entered, cannot be left under the transition rule.
A simple representation is a self-loop:
\[ A\to A. \]Absorbing states become especially important in stochastic processes.
Cycles in State Spaces
A cycle occurs when a sequence of transitions returns to a previous state.
For example,
\[ A\to B\to C\to A. \]Repeatedly following the same transitions can create periodic behavior.
Fixed States
Under a deterministic update function \(F\), a state \(s^*\) is fixed when
\[ F(s^*)=s^*. \]Once reached, the state does not change.
A fixed state is a one-state cycle.
State-Space Size
State spaces can grow rapidly.
If \(n\) independent binary components are present, then
\[ |S|=2^n. \]For
\[ n=20, \]this already gives
\[ 2^{20}=1{,}048{,}576 \]states.
Combinatorial Explosion
Combinatorial explosion refers to the rapid growth of possible configurations as components or choices increase.
Even when each component has only a few possible values, the total product can become enormous.
This is one reason state-space search and optimization can become difficult.
Example: Three Component Types
Suppose a system has:
- 4 locations;
- 3 modes;
- 2 power states.
The unconstrained state count is
\[ 4\cdot3\cdot2=\boxed{24}. \]Encoding States as Integers
Finite states can often be assigned integer labels.
For four binary states,
\[ 00,\quad01,\quad10,\quad11, \]we might assign
\[ 0,\quad1,\quad2,\quad3. \]Such encodings can simplify storage and computation.
Encoding States as Bit Strings
Binary systems are naturally encoded as bit strings.
A configuration
\[ (1,0,1,1,0) \]may be stored as
\[ 10110. \]Each bit represents one binary state variable.
Encoding Categorical States
Components with more than two values can still be encoded numerically.
For example,
\[ \text{low}\mapsto0,\qquad \text{medium}\mapsto1,\qquad \text{high}\mapsto2. \]Encoding changes representation, not the underlying state structure.
State Tables
A finite state space can be listed explicitly in a table.
| State ID | Switch 1 | Switch 2 |
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 2 | 1 | 0 |
| 3 | 1 | 1 |
Transition Tables
A deterministic finite system can list each current state together with its next state.
| Current state | Next state |
|---|---|
| A | B |
| B | C |
| C | C |
This table defines the update function completely.
State-Space Search
A search algorithm may explore a state space by starting from an initial state and generating successor states.
Each newly discovered state becomes another candidate for exploration.
Graph-search methods later formalize this process.
Visited States
Search procedures often record which states have already been visited.
Without such a record, a cycle such as
\[ A\to B\to C\to A \]could cause repeated exploration of the same states indefinitely.
Goal States
A goal state satisfies the objective of a search or problem-solving process.
A puzzle solver may search for a solved configuration.
A routing problem may search for a destination state.
A scheduling algorithm may search for any feasible complete assignment.
Costed State Spaces
Transitions may have costs.
If moving from state \(s\) to state \(t\) costs
\[ c(s,t), \]then a trajectory has total cost equal to the sum of its transition costs.
This creates a weighted state graph.
State Spaces in Games
A game state records all information needed to continue play.
This might include:
- piece positions;
- whose turn it is;
- scores;
- remaining resources;
- special rule conditions.
Legal moves define transitions between game states.
State Spaces in Scheduling
A scheduling state may specify which tasks have been assigned, which remain, and which resources are occupied.
Constraints eliminate configurations that violate timing, capacity, or dependency rules.
A feasible schedule is therefore one valid state or completed path through a scheduling state space.
State Spaces in Networks
A network state might specify which links are active, which nodes are functioning, or how much flow occupies each connection.
With many binary links, the configuration count may grow as
\[ 2^n. \]Reliability problems often study which such configurations preserve connectivity.
State Spaces in Probability
A sample space can often be interpreted as a state space of possible outcomes.
For three coin flips,
\[ \Omega= \{HHH,HHT,HTH,HTT,THH,THT,TTH,TTT\}. \]Each outcome is a complete configuration of three binary trials.
State Spaces in Algorithms
An algorithm's state may include variables, data structures, counters, and control position.
Each computation step changes one state into another.
This perspective allows algorithm execution to be studied as movement through a discrete state space.
Equivalent State Descriptions
Two different encodings may describe the same underlying state.
For example,
\[ (\text{on},\text{off},\text{on}) \]and
\[ 101 \]may represent the same configuration under a chosen coding scheme.
Representation should not be confused with the represented state.
Redundant State Variables
A state description is redundant when some component can be determined from the others.
For example, if
\[ z=x+y \]always holds, then storing all three of
\[ (x,y,z) \]may contain unnecessary information.
Compressed State Descriptions
A state representation can sometimes be compressed while preserving all information relevant to future behavior.
Efficient state representations matter because they reduce storage and search complexity.
The best representation depends on the problem.
State-Space Partitions
A state space may be partitioned into classes sharing a property.
For example, binary strings of length \(n\) may be grouped by the number of ones they contain.
Every state belongs to exactly one such class.
Example: Partition by Parity
Consider integer states
\[ S=\{0,1,2,3,4,5\}. \]Partition them into
\[ E=\{0,2,4\} \]and
\[ O=\{1,3,5\}. \]The blocks classify states by parity.
State Invariants
A state invariant is a property that remains unchanged across all allowed transitions.
If every legal move preserves parity, then parity is an invariant of the state process.
Invariants can prove that some states are unreachable.
Example: Reachability from an Invariant
Suppose a system begins in an even-numbered state and every legal transition changes the state by an even number.
Then every reachable state remains even.
Any odd state may belong to the broader state space but cannot be reached from that initial state.
State Constraints versus Transition Constraints
A state constraint says which configurations are allowed.
A transition constraint says which moves between allowed states are permitted.
These are different layers of the model.
Example: Legal States, Restricted Moves
Suppose every square on a grid is a legal location.
The state space contains all grid positions.
But the transition rule may permit movement only to adjacent squares.
State legality and move legality are therefore distinct.
Finite and Countably Infinite State Spaces
A state space may be finite, such as
\[ \{0,1\}^8, \]or countably infinite, such as
\[ \mathbb{N} \]for a queue length.
The same structural ideas of configuration, transition, and reachability apply in both cases.
Common Error: Counting Partial Descriptions as Complete States
Suppose a system requires
\[ (\text{location},\text{direction}) \]to determine its state.
Listing only
\[ \text{location}=A \]does not identify one unique state because the direction is still unknown.
Common Error: Counting Forbidden Configurations
Multiplying component counts gives the unconstrained Cartesian product.
If some combinations violate model rules, they must be removed.
Therefore
\[ |S_1|\cdots|S_n| \]is not automatically the number of feasible states.
Common Error: Confusing Possible with Reachable
A state may satisfy every static constraint but still have no transition path from the chosen initial state.
Reachability depends on the transition structure, not only on state validity.
Common Error: Confusing State with Path
The state
\[ B \]is one condition.
The sequence
\[ A\to B\to C \]is a trajectory through three states.
One is a point in state space; the other is a path through it.
Common Error: Treating Encoding as Structure
Labeling four states
\[ 0,1,2,3 \]does not mean the states themselves have arithmetic relationships.
The labels may be only identifiers.
Common Error: Ignoring Initial Conditions
The same transition graph can produce different reachable sets from different starting states.
Reachability statements should therefore specify the initial state or set of initial states.
A Reliable Procedure for Building a State Space
- Identify the information needed to describe one complete state.
- Choose state variables for that information.
- List the possible values of each state variable.
- Form the unconstrained Cartesian product.
- Apply all feasibility constraints.
- Choose an efficient state encoding.
- Identify initial states.
- Define allowed transitions.
- Determine reachable, terminal, fixed, or goal states as needed.
- Use graphs, tables, or search procedures to analyze the resulting system.
Example: Full State-Space Construction
Suppose a device has:
- power state \(P\in\{0,1\}\);
- mode \(M\in\{A,B,C\}\).
The unconstrained state space is
\[ \{0,1\}\times\{A,B,C\}. \]It contains
\[ 2\cdot3=6 \]states:
\[ (0,A),(0,B),(0,C),(1,A),(1,B),(1,C). \]If mode \(C\) is forbidden when power is off, remove \((0,C)\).
The feasible state space then has
\[ \boxed{5} \]states.
Practice 1: Binary State Count
A system has five independent binary components.
How many configurations are possible?
Practice 2: Product State Space
One component has \(3\) states and another has \(4\) states.
How many unconstrained combined states are possible?
Practice 3: Complete Configuration
A robot state requires both location and direction.
Is the description
\[ \text{location}=A \]by itself a complete state?
Practice 4: Forbidden State
Two binary switches may not both be on.
List the feasible states.
Practice 5: Reachability
Suppose
\[ A\to B,\qquad B\to C. \]Starting from \(A\), is \(C\) reachable?
Practice 6: Unreachable State
Let
\[ S=\{A,B,C,D\} \]with transitions
\[ A\to B,\qquad B\to C. \]Starting from \(A\), which listed state is unreachable?
Practice 7: Deterministic or Not?
From state \(A\), both
\[ A\to B \]and
\[ A\to C \]are allowed.
Does this define a deterministic next-state function?
Practice 8: Fixed State
Suppose
\[ F(A)=B,\qquad F(B)=B. \]Which state is fixed?
Practice 9: Trajectory or State?
Is
\[ A,B,C,D \]best interpreted as one state or as a trajectory when these symbols record successive system conditions?
Practice 10: Constrained Product
A system has \(2\) power states and \(3\) modes, producing \(6\) unconstrained configurations.
If two configurations are forbidden, how many feasible states remain?
Practice Answers
Practice 1
\[ \boxed{2^5=32}. \]Practice 2
\[ \boxed{3\cdot4=12}. \]Practice 3
No. If direction is part of the state definition, then location alone is incomplete.
Practice 4
The unconstrained states are
\[ (0,0),(0,1),(1,0),(1,1). \]Remove \((1,1)\):
\[ \boxed{\{(0,0),(0,1),(1,0)\}}. \]Practice 5
Yes. The path
\[ A\to B\to C \]proves reachability.
Practice 6
No path from \(A\) reaches \(D\).
\[ \boxed{D} \]is unreachable from \(A\).
Practice 7
No. State \(A\) has two possible successors, so the transition rule is not single-valued without an additional selection rule.
Practice 8
Since
\[ F(B)=B, \]the fixed state is
\[ \boxed{B}. \]Practice 9
It is a trajectory because it records several successive states in order.
Practice 10
\[ 6-2=\boxed{4}. \]What to Remember
- A configuration is one complete description of a discrete system.
- A state space is the set of all states allowed by the model.
- Cartesian products combine component state sets.
- Binary systems with \(n\) independent components have \(2^n\) configurations.
- Constraints reduce the unconstrained configuration space.
- Possible states and reachable states are not always the same.
- Transitions define a relation or function on the state space.
- A trajectory is a sequence of states, not a single configuration.
- State encodings may change representation without changing the underlying state.
- Large state spaces can grow combinatorially and become difficult to search.
The central habit is: define exactly what information makes one state complete, then separate allowed configurations from the transitions that connect them.
Where We Go Next
State spaces collect many discrete objects, but different objects may still share the same structural role or classification. Grouping objects according to an equivalence relation produces equivalence classes.
The next lesson, Equivalence Classes, develops this relationship between equivalence, partitions, canonical groupings, and quotient structures.