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 Ω(8~(n/5)) and less than (_(n+1)~(2n)), 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)) (mn(log n—log m))~(1/2).
展开▼
