Motivation
A finite automaton describes a possibly infinite language, but many questions about that language can be answered by inspecting a finite graph. Reachability decides whether any accepted word exists; a product graph compares two machines; and a useful cycle distinguishes finite from infinite languages. These algorithms also produce certificates: an accepted word, a distinguishing word, or a path through a cycle that can be repeated.
The machines here are complete deterministic finite automata over the same finite alphabet. The graph underlying an automaton retains labeled transitions. Reachability disregards labels while searching, but labels are needed to turn a path back into a word.
Definitions
Definition 1.3.1
(Deterministic finite automaton and acceptance)
A DFA is , with finite state set , start state , accepting set , and total transition function . The extended transition is defined by following the letters of in order. An accepted word ends in after being read from .
Definition 1.3.2
(Reachable, co-reachable and useful)
A state is reachable if a path from reaches it. It is co-reachable if some path from it reaches an accepting state. A directed cycle is useful if it lies on a path from the start to an accepting state; equivalently, its vertices are both reachable and co-reachable. A cycle must contain at least one transition. The empty word labels a length-zero path but is not a cycle for this purpose.
Definition 1.3.3
(The three decision problems)
- Emptiness. Input: a DFA . Output: whether , together with an accepted word when the language is not empty.
- Equivalence. Input: two complete DFAs over the same alphabet. Output: whether , together with a word accepted by exactly one of them when they differ.
- Infinitude. Input: a DFA . Output: whether is infinite, together with labeled entry, cycle and exit paths when it is.
Theorems
Theorem 1.3.4
(Emptiness and equivalence)
The language of a DFA is empty exactly when no accepting state is reachable. Two complete DFAs over the same alphabet are equivalent exactly when no reachable state of their product has precisely one accepting component. Breadth-first search either decides the corresponding property or returns a shortest witness word.
Proof
(Search order and the product state)
A word labels a path from the start, and every path's labels form a word. Its endpoint is accepting exactly when the word is accepted, proving the emptiness criterion. Breadth-first search explores states in nondecreasing path length; predecessor edges recover a shortest path to an accepting state when one exists.
For equivalence, the product state after reading is , by induction on the length of . Mark a pair accepting for the difference test when exactly one component is accepting. A reachable marked pair is reached by a word accepted by exactly one machine; conversely every distinguishing word reaches such a pair. Searching the finite product graph therefore decides equivalence and, if it fails, returns a shortest distinguishing word.
Proof sketch or proof idea
Theorem 1.3.5
(Infinitude criterion)
A DFA language is infinite exactly when its transition graph has a useful directed cycle. If the automaton has states and its language is finite, every accepted word has length less than .
Proof
(Repeating a useful cycle, and the pigeonhole principle)
If a useful cycle exists, choose a path from the start to a cycle vertex, traverse the cycle times, and then follow a path to an accepting state. The cycle label has positive length, so the accepted words for have distinct lengths. The language is infinite. Conversely, an accepted word of length at least visits states along its run, including the start. Two visited states coincide by the pigeonhole principle. Choose the first repeated state in the run; the transitions from its earlier occurrence to that repeat form a nonempty cycle with no internal repeated state on an accepting path. If the language is infinite, some accepted word has length at least , because only finitely many words over a finite alphabet have smaller length. This proves both the converse and the finite-language length bound.
Proof X-ray
The cycle must be useful
A reachable cycle can be repeated, but that alone does not give accepted words. The proof uses three pieces in order: an entry path to the cycle, the nonempty cycle, and an exit path to an accepting state. Usefulness is exactly the condition that the exit path exists from the cycle's own vertices; the rejecting sink in the counterexample below fails it.
Three further hypotheses enter. The cycle must contain a transition: the words for different repetition counts are distinct because their lengths differ by multiples of the cycle label's positive length. Finiteness of drives the converse: an accepting run of length at least visits states, so the pigeonhole principle forces a repeat, and choosing the first repeat keeps the cycle on the accepting run, which is why the cycle it produces is automatically useful. Finally, the length bound uses finiteness of the alphabet, since only finitely many words are shorter than .
Worked examples
Worked example 1.3.6
(An empty language with a reachable cycle)
A one-state DFA whose only state is nonaccepting and loops on every letter has a reachable cycle but accepts nothing. Its cycle is not co-reachable to an accepting state. Reachability of an accepting state fails, so the language is empty and therefore finite.
Worked example 1.3.7
(A shortest distinguishing word)
Compare the binary DFA accepting words with an even number of ones with the DFA accepting words ending in zero. The empty word is accepted by the parity machine and rejected by the ending-zero machine. The product start state is already marked, so breadth-first search returns as a shortest distinguishing word.
Worked example 1.3.8
(A useful cycle gives infinitely many words)
Over , let the start state loop on , transition on to an accepting state, and send every further input to a rejecting sink. The language is . The start loop is useful because the transition reaches an accepting state, and repeating the loop produces infinitely many accepted words.
Common mistakes
Counterexample mode
A cycle outside all accepting paths
A reachable rejecting sink loops forever, but no accepting state can be reached from it. Repeating that loop gives infinitely many rejected words, not infinitely many accepted words. Co-reachability is essential.
Common mistake
(State counts and diagrams do not decide equivalence)
Two automata may have different numbers of states and still recognize the same language. Equality of diagrams or state counts is not the equivalence test. For example, a one-state DFA accepting every word over and a two-state DFA whose states both accept and exchange places on recognize the same language .
Common mistake
(A long accepted word does not make a language infinite)
A finite language can contain long words: the length bound depends on the number of states of the particular DFA, and it applies only after infinitude has been ruled out. Over , a chain followed by a rejecting sink, with only accepting, accepts just . The automaton has six states, and the single accepted word is shorter than six.
Searching the graphs
For emptiness, start a breadth-first search at and follow each transition out of every discovered state. Mark each state when first discovered and record the preceding state and transition label. If an accepting state is reached, following predecessor pointers back to and reversing the labels yields a witness. If the start state is already accepting, the witness has length zero. If the search ends without discovering an accepting state, no word can be accepted because every transition path from the start has been explored.
For infinitude, first mark states reachable from the start. Then reverse every transition edge and search from all accepting states simultaneously. The states reached in this reverse search are precisely those from which an accepting state is reachable in the original graph. Restrict attention to states marked by both searches, and test the induced directed graph for a cycle. A depth-first search or a strongly connected component algorithm can perform this test. A singleton component contains a cycle only if it has a self-loop; a component with at least two vertices contains a directed cycle.
If a cycle is found in that restricted graph, the two reachability searches can supply the entry and exit paths, and the cycle search supplies the repeated segment. Their labels give a concrete infinite family. The entry and exit paths need not be simple, although simple paths can be chosen. Each repetition of the cycle increases word length by the positive length of its label, so there is no possibility that two different repetition counts describe the same word.
Worked example 1.3.9
(A finite language and an irrelevant cycle)
Over the unary alphabet , let , with looping on , and let only be accepting. The language is . All three states are reachable, but cannot reach the accepting state, so its self-loop is not useful. The states both reachable and co-reachable are , and their induced graph is acyclic.
Product machines and witness length
Definition 1.3.10
(Product automaton and marked pairs)
For DFAs with state sets , the product has at most states and transition
For equivalence, mark a pair exactly when one component accepts and the other rejects. The product itself need not be minimized. Unreachable pairs can be ignored because no input can lead to them from the product start.
Theorem 1.3.11
(Length of a shortest distinguishing word)
If the languages of two complete DFAs over the same alphabet differ, then some word accepted by exactly one of them has length at most , and breadth-first search of the product returns a shortest such word.
Proof
(Cutting out a repeated product state)
If the languages differ, a shortest distinguishing path never repeats a product state. If it did, delete the segment between two occurrences of that state; the remaining labeled path would reach the same marked endpoint with a shorter word. Therefore a shortest distinguishing word has length at most .
This is a finite bound for the product construction, not a requirement to enumerate every word up to that length. Breadth-first search visits states and transitions instead of explicitly generating all possible words.
The same product graph supports other comparisons by changing which pairs are marked. To test whether , mark pairs whose first component accepts and second rejects. A reachable marked pair is a counterexample to inclusion. To test disjointness, mark pairs whose two components both accept. A reachable marked pair supplies a common word. The correctness argument remains the induction on the two simultaneous runs; the interpretation of the accepting condition changes with the question.
Completeness and alphabets
The complement of a complete DFA over a fixed alphabet is obtained by exchanging accepting and nonaccepting states. Completeness matters: for every word there must be exactly one run ending in a state. In a partial transition diagram, a missing transition is usually interpreted as rejection. Merely swapping accepting marks does not turn such a missing run into acceptance, so it can give the wrong complement. Add a rejecting sink with all missing transitions before swapping marks.
Counterexample mode
Swapping marks needs a complete DFA
Claim: exchanging accepting and nonaccepting states always gives the complement. Over , take the partial diagram with one accepting state and only the transition . Its language is . Swapping marks leaves no accepting state, so the new machine accepts nothing, whereas the complement of contains . Complete the diagram first, with a rejecting sink , and ; swapping then makes the only accepting state, and the machine accepts exactly the words that contain a , which is the complement.
When comparing automata, specify a common alphabet. If one machine lacks transitions for a symbol in that alphabet, complete it with a rejecting sink as needed. The choice of ambient alphabet is part of the question: complement means all words over that alphabet that are not in the language. Treating a symbol as outside the alphabet in one place and as an automatically rejected input in another can make an unstated change to the problem.
Complexity and certificates
Proposition 1.3.12
(Running time of the graph searches)
For a complete DFA with states over an alphabet of size , a graph search takes time and search marks, apart from storing the input table and any reverse edges. Emptiness needs one such search; infinitude needs two reachability searches and a cycle test on the induced graph, each of this order. The product search for equivalence visits at most states and transitions.
Proof
(Counting states and transitions)
A complete transition table has labeled transitions. Each search marks a state when it is first discovered and examines each outgoing transition once, which gives the stated bound. The reverse graph may have many incoming edges at a state but has the same total number of edges. The product has at most states, each with successors, so its search obeys the analogous bound; it can generate successors on demand instead of storing every product edge.
A shortest accepted or distinguishing word is a positive certificate that can be checked by simulating one or two automata. A claim of emptiness or equivalence has a different certificate: the set of states reachable from the relevant start, together with the fact that it contains no forbidden endpoint and is closed under every transition. One can verify closure by checking all outgoing labeled transitions. A failed attempt to find a short word is not enough unless the search has exhausted the finite reachable state set or another justified bound is used.
The infinitude certificate consists of labeled entry, cycle and exit paths. Checking their endpoints and the accepting status verifies the whole infinite family. Conversely, absence of a useful cycle can be certified by a topological ordering of the reachable co-reachable subgraph. These certificates make the graph proof concrete and distinguish a terminating algorithm from a hand-waving claim that an infinite language has been inspected word by word.
Summary
Graph reachability turns language emptiness into a finite search. A product automaton turns inequivalence into reachability of a disagreement. An accepting path with a nonempty cycle gives infinitely many distinct accepted lengths, and every sufficiently long accepting path contains such a cycle.
Exercises
Quick check
(A DFA start state is accepting. Is its language empty? Give a witness.)
Read off the run of the empty word.
Solution · Answer
No. The empty word leaves the machine in its accepting start state and is a witness.
Quick check
(If two DFAs disagree on the empty word, what does the product search return?)
Check the product start state.
Solution · Answer
It returns the empty word: the product start state itself has exactly one accepting component, so no transition is needed.
Quick check
(Why can a useful cycle be traversed arbitrarily many times without changing the state from which the exit path starts?)
Where does the cycle begin and end?
Solution · Answer
A cycle starts and ends at the same state. After each traversal the exit path is available from that same state.
Quick check
(A four-state DFA accepts a word of length four. Can its language be finite?)
Count the states visited by the accepting run.
Solution · Answer
No. The accepting run visits five states counting the start, so some state repeats. The intervening nonempty cycle is useful and can be repeated to generate infinitely many accepted words.