Given a finite automaton, how do you decide whether it accepts infinitely many strings rather than a finite set?
answer
- infinite needs a loop
- not every loop counts
- reachable from the start
- and still able to accept
- cycle on the live sub-graph
basics
~20 sFiniteness is a cycle test on the useful part of the graph. Keep the states that are both reachable from the start and able to reach an accepting state; if that live sub-graph contains a cycle, the language is infinite, otherwise it is finite.
solid answer
~40 sAcceptance is a path from the start state to an accepting state, so the language is infinite exactly when arbitrarily long such paths exist — which happens exactly when some path can loop. But not every loop counts. A cycle in an unreachable region contributes nothing, and neither does a cycle from which no accepting state can still be reached. So compute two sets: states **reachable** from the start, by a forward search, and states **co-reachable**, meaning some accepting state is reachable from them, by a search on reversed edges. Intersect them to get the **live** states, and test the sub-graph they induce for any cycle. A cycle there means you can go round it as often as you like and still finish in an accepting state, so infinitely many strings are accepted.
code
pseudocode · 15 linesR <- states reached by forward search from the start state
C <- states reached by search from all accepting states
along reversed edges // can still reach acceptance
live <- R intersect C
if live is empty:
return "empty language" // nothing accepted at all
keep only edges whose two endpoints are both in live
if that sub-graph contains a cycle:
return "infinite"
else:
return "finite"go deeper
Hold on to the distinction: a machine always has finitely many states, but it can still accept infinitely many strings, because a loop can be traversed any number of times.
Explain the two searches and why both are needed — forward for reachability, backward along reversed edges for the ability to still reach acceptance — then the cycle test on what survives.
Use it as a diagnostic on machines your pipeline generated: unintended live loops mean a rule matches far more than intended, and the dead states the searches expose are safe to delete.
Decide where the guarantee belongs. If a rule format must only ever match a bounded set, enforce finiteness at build time rather than hoping reviewers spot the loop.
## What the question really asks A finite automaton always has finitely many states, but the language it accepts can be finite or infinite. "Finite" here means the set of accepted **strings** is finite — a rule that matches a fixed handful of messages — while "infinite" means it matches unboundedly many. The question comes up whenever someone claims a pattern is safe because it "only matches a few things", and it is decided by a graph traversal rather than by enumeration. ## Live states: reachable and co-reachable Every accepted string corresponds to a path from the start state to an accepting state, with the string spelled by the edge labels. A state matters only if it can sit on such a path, which needs two independent properties: - **Reachable**: some input drives the machine from the start into this state. Found by a forward search from the start state. - **Co-reachable**: from this state, some further input drives the machine into an accepting state. Found by searching **backwards** along reversed edges from the accepting states. Call the intersection the **live** states. Everything outside it — an orphaned component, a trap with a self-loop, a region whose accepting states were removed by an earlier construction — is irrelevant to the language and must be discarded before you look for cycles. Skipping this step is the classic wrong answer, because a trap state's self-loop is a cycle and it proves nothing at all. ## The decision procedure 1. Forward search from the start state; collect the reachable states. 2. Backward search from the accepting states along reversed edges; collect the co-reachable states. 3. Intersect to get the live states, and keep only edges with both endpoints live. 4. Test that sub-graph for a cycle, with any standard cycle detection. 5. Cycle found means **infinite**; no cycle means **finite**. The cost is linear in states plus edges, so the answer is cheap even for large machines. Step four also gives you a concrete witness family: pick a live cycle, take the string spelled from the start to the cycle, the string around it, and the string from the cycle to an accepting state. Repeating the middle piece any number of times yields an infinite family of accepted strings, which is what "infinite" means made concrete. ## The length-window characterisation There is an equivalent test that avoids the two searches and is worth knowing because it explains *why* the cycle test works. Let `n` be the number of states. A run on a string of length `n` visits `n + 1` states, so by the pigeonhole principle **some state repeats**, which means the run went round a cycle — and since the run is accepting, that cycle is live. Conversely a live cycle can be entered and left within a bounded number of steps. This gives the standard statement: the language is infinite exactly when the machine accepts some string whose length lies in the window from `n` up to `2n - 1`. You never need to look further than `2n - 1`, because a longer accepted string can always be shortened into that window by removing a repeated segment. As a decision procedure it is far more expensive than the graph test, since the window still contains exponentially many candidate strings, but as an explanation it is the reason the graph test is correct. ## Where it shows up | situation | what the test tells you | |---|---| | a validation rule claimed to match "a fixed set of codes" | whether the machine really does accept only finitely many inputs | | a machine produced by a chain of closure operations | whether an intermediate step left live loops you did not intend | | pruning a compiled rule table | dead states found by the two searches can be deleted outright | | bounding a generated test corpus | a finite language can be enumerated exhaustively; an infinite one cannot | The useful habit is the two searches themselves. Reachability and co-reachability are the same primitives that decide emptiness — a language is empty exactly when no accepting state is reachable, that is, when the live set is empty — so one traversal pass answers both questions, and the leftovers are exactly the states a compiler can drop.
- A machine's transition graph clearly has a cycle, yet its language is finite. How?The cycle is not live. Either no input reaches it from the start state, or no accepting state can be reached from it — a trap state with a self-loop is the everyday case. Going round such a cycle can never be part of an accepting run, so it contributes no accepted strings.
- Why is it enough to look at accepted strings no longer than twice the state count?Any accepting run on a longer string must revisit a state, and cutting out the segment between the two visits leaves a shorter accepted string. Repeating that shortening lands in the window from the state count up to twice it minus one, so if nothing in that window is accepted, nothing longer is either and the language is finite.
- How do the same two searches decide whether the language is empty?Emptiness is the case where the live set itself is empty: no accepting state is reachable from the start, equivalently no state is both reachable and co-reachable. One traversal pass therefore answers emptiness and finiteness together, and identifies every state a compiler can delete without changing the language.
A road network offers unboundedly many routes only if some roundabout sits on a road you can actually drive onto and can actually leave towards your destination. A roundabout inside a fenced-off industrial estate adds no routes at all.
saying these in an interview costs you the question
- Says any cycle in the transition graph makes the language infinite
- Counts accepting states and calls a machine with many of them infinite
- Proposes enumerating strings until the answer becomes obvious
- Ignores whether an accepting state is still reachable from the cycle
- Believes finiteness of a finite automaton's language is undecidable
- Confuses finitely many states with finitely many accepted strings