Automaticity I: Properties of a Measure of Descriptional Complexity

摘要

LetΣandΔbe nonempty alphabets withΣfinite. Letfbe a function mappingΣ* toΔ. We explore the notion ofautomaticity, which attempts to model how “close”fis to a finite-state function. Formally, the automaticity offis a functionAf(n) which counts the minimum number of states in any deterministic finite automaton that computesfcorrectly on all strings of length ⩽n(and its behavior on longer strings is not specified). We defineAL(n) for languagesLto beAχL(n), whereχLis the characteristic function ofL. The same or similar notions were examined previously by Trakhtenbrot, Grinberg and Korshunov, Karp, Breitbart, Gabarró, Dwork and Stockmeyer, and Kaneps and Freivalds. Karp proved that ifL⊆Σ* is not regular, thenAL(n)⩾(n+3)/2 infinitely often. We prove that the lower bound is best possible. We obtain results on the growth rate ofAf(n). If |Σ|=k⩾2 and |Δ|=l<∞, thenAf(n)⩽C(1+o(1)) kn+2/nforC=(logk l)/(k−1)2. Also, for almost all functionsfand anyε>0 we haveAf(n)>(1−ε) Ckn+1/nfor all sufficiently largen. We also obtain bounds onNL(n), the nondeterministic automaticity function. This is similar toAf(n), except that it counts the number of states in the minimal NFA, and it is defined for languagesL⊆Σ*. For |Σ|=k⩾2, we haveNL(n)=O(kn/2). Also, for almost all languagesLand everyε>0 we have [formula]for all sufficiently largen. We prove some incomparability results between the automaticity measure and those defined earlier by Gabarró and others. Finally, we examine the notion of automaticity as applied to sequences.