Limitedness theorem on finite automata with distance functions

摘要

A finite automaton A with a distance function d is a sextuple, 〈Σ, Q, M, S, F, d〉, such that Σ is the input alphabet, Q is the finite set of states, M: Q × Σ → 2Q is the transition function, S ⊂ Q and F ⊂ Q are the sets of initial and final states, respectively, d: Q × Σ × Q → {0, 1, ∞} is the distance function, where ∞ denotes infinity, and d satisfies the following: for any (q, a, q′) ∈ Q × Σ × Q, d(q, a, q′ = ∞ iff q′ ∉ M(q, a). M is extended toQ × Σ∗ and d is extended to Q × Σ∗ × Q in the usual way. A is said to be limited in distance if there exists a nonnegative integer k such that for any w accepted by A, d(q, w, q′) ⩽ k for some q ∈S and q′ ∈ F. This paper shows that there exists an algorithm for deciding whether or not an arbitrary finite automaton with a distance function is limited in distance.