STEP-BY-STEP LESSON · §12.3
Simplifying Finite-State Automata
Merge states only when every continuation gives the same acceptance behavior.
Before you begin
A deterministic finite automaton
A DFA has a finite set of states and an input alphabet. It specifies a start state, accepting states and exactly one next state for each state-symbol pair. Read the entire input left to right; the word is accepted exactly when the resulting state is accepting. For ε, the resulting state is the start state.
Words, alphabet and empty word
An alphabet is a finite set of allowed symbols. A word is a finite sequence of them; order and repetitions matter. ε is the empty word, with length 0. The language {ε} contains one word, whereas ∅ contains none.
Symbols
- p~q
- states are indistinguishable by continuation acceptance
Definitions and notation for this topic
Equivalent DFA states
p∼q
Two states of a DFA are equivalent when every finite continuation word is accepted from p exactly when it is accepted from q.
Include the empty continuation: an accepting state and a nonaccepting state are already distinguished by ε. The sign ∼ here is state equivalence, not propositional negation.
Separate glossary example
If p and q are both accepting and each loops to itself on every alphabet symbol, they are equivalent: every continuation is accepted from both.
Step by step
Step 1 / 6
Compare future words
Two states are equivalent if every possible continuation is accepted from both or rejected from both.
Names and drawing positions are irrelevant.
Worked example
Over {0,1}, A,B are accepting and any symbol from either leads to A. C rejects and loops to itself on either symbol. Which states are equivalent?
- A and B accept ε and every nonempty continuation: after the first symbol, the state is A.
- C rejects ε, so it is already distinguishable from A and B.
- A,B can be merged; C stays separate. Removing unreachable states depends on the chosen start.
Optional self-check
States p and q both reject, but 1 takes p to an accepting state and q to a rejecting one. Can p and q be merged?
Show answer
No. The continuation 1 is accepted from p and rejected from q, so it distinguishes them despite their matching current status.