The maximum length of shortest accepted strings for direction-determinate two-way finite automata

Abstract

It is shown that, for every $n⩾2$, the maximum length of the shortest string accepted by an $n$-state direction-determinate two-way finite automaton is exactly $\left(\genfrac{}{}{0ex}{}{n}{\lfloor \frac{n}{2}\rfloor }\right)-1$ (direction-determinate automata are those that always remember in the current state whether the last move was to the left or to the right). For two-way finite automata of the general form, a family of $n$-state automata with shortest accepted strings of length $\frac{3}{4}\cdot 2^n-1$ is constructed.

14 pages, 8 figures