A deterministic finite automaton is described by finite state and alphabet label lists, one initial state label, an accepting-state bit mask, and a finite transition table. Keep each label in increasing order and list transitions lexicographically by the actual state and alphabet labels. This retains arbitrary finite subsets of the permitted labels, rather than assuming they are consecutive.
The prime-exponent encoding of a finite list gives an explicit Gödel encoding for a list of nonnegative integers:where is the th prime number. Encode the descriptor as a list beginning with the numbers of states and alphabet symbols, followed by their sorted labels, the start label, the accepting mask, and all transition destinations. The lengths are then known during decoding.
Unique prime factorization recovers the list and hence the automaton. Reject an integer if the prescribed prime exponents are missing, additional primes occur, the list lengths disagree, state or alphabet labels repeat, the initial state or a transition target is absent, or the mask is out of range. These are effective finite checks. Thus every automaton has an integer code, valid codes are decidable, and the transition system of a coded automaton is computable. Invalid integers may be excluded explicitly or assigned a fixed empty-language automaton.
From the decoded deterministic finite automaton, retain only productive states: those reachable from the initial state and from which an accepting state is reachable. Both sets are computable by finite graph search. Its regular language is infinite precisely when this productive directed graph contains a directed cycle.
Indeed, a cycle on a route from the start to acceptance can be repeated arbitrarily often, giving accepted words of different lengths. Conversely an accepted path of length at least the number of productive states repeats one such state and gives a productive cycle. Therefore absence of cycles bounds every accepted length strictly below that number. Cycle detection is a finite algorithm, proving that finiteness of the accepted language is decidable.
When it is finite, enumerate every word of length less than the number of states and simulate acceptance, then count the accepted words. This includes the empty word. Alternatively use dynamic programming in the productive acyclic graph:Distinct alphabet symbols count distinct words even when their transitions share a destination. The result is , or zero if the start state is not productive. Validity of the encoding is checked first, so the set of valid finite-language codes is recursive set.
Articles by others on the same topic
There are currently no matching articles.