On the Length of Shortest Strings Accepted by Two-way Finite Automata

Abstract

Given a two-way finite automaton recognizing a non-empty language, consider the length of the shortest string it accepts, and, for each n ≥ 1, let f(n) be the maximum of these lengths over all n-state automata. It is proved that for n-state two-way finite automata, whether deterministic or nondeterministic, this number is at least Ω(10^n/5) and less than $\left(\begin{array}{c}2n\\ n+1\end{array}\right)$ , with the lower bound reached over an alphabet of size Θ(n). Furthermore, for deterministic automata and for a fixed alphabet of size m ≥ 1, the length of the shortest string is at least $e^{(1+o(1))\sqrt{mn(\log n-\log m)}}$ .