论文标题
方向确定的双向有限自动机的最大最短接收字符串长度
The maximum length of shortest accepted strings for direction-determinate two-way finite automata
论文作者
论文摘要
结果表明，对于每$ n \ geqslant 2 $，由$ n $ n $ state方向所接受的最大字符串的最大长度完全确定的双向有限自动机是$ \ binom {n} {\ lfloor \ lfloor \ lfloor \ frac {n} {n} {2}} {2} \ rfloor} $（rfloor} $（rfloor} $（rfloor} $ 1 $（方向）在左侧或右侧）。对于通用形式的双向有限自动机，构建了$ n $ n $ state自动机的家族，其长度最短的字符串$ \ frac {3} {4} {4} \ cdot 2^n-1 $是构建的。
It is shown that, for every $n \geqslant 2$, the maximum length of the shortest string accepted by an $n$-state direction-determinate two-way finite automaton is exactly $\binom{n}{\lfloor\frac{n}{2}\rfloor}-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.
