Claim: If $M$ is a 2-way NFA (without endmarkers) with $n$ states
which acceptes a unary language $L\not=\emptyset$ then there is a word $w \in L$ of
length at most $3n+5$.
Proof sketch:
Let $v\in L$ be some word of some length $N>3n+5$ and let $\rho$ be
an accepting run for $v$. Let $v=v_1 v_2$, where $v_2$ is the suffix
of $v$ of length $n+1$. Let $\rho=\rho_1\rho_2$, where $\rho_1$ is
the prefix of $\rho$ that ends when the head moves from the last
position of $v_1$ to the right, for the last time. Let $q$ be the last
state of $\rho_1$.
Before we manipulate $\rho_1$, we first prepare a "way out" for $M$ by
showing that we can pump up (!) $\rho_2$.
For each of the $n+1$ positions $i$ of $v_2$ let $p_i$ be the first
state in which this position is visited in $\rho_2$. Clearly, there
must be positions $i<j$ with $p_i=p_j$ and thus we can pump up
$\rho_2$ by strings whose length are multiples of $j-i$, if we like. (This will not affect
$\rho_1$ and the subrun $\rho'_1$ that will be described below).
However, the main part of the construction is to transform $\rho_1$
into a subrun $\rho'_1$ on the string $u$ of length $2n+3$. The idea is to
center $\rho'_1$ around position $n+2$ and neither let it get to
position 1 nor to position $2n+3$. The construction will make sure
that $\rho'_1$ ends in state $q$ at some position (between 2 and 2n+2). It
can then be completed to an accepting run by adding a suitably pumped
version of $\rho_2$ that makes sure that the overall string $uv'_2$
has length at least $2n+2$ (but at most $3n+4$).
Let $\rho_0$ be the prefix of $\rho_1$ until position $n+2$ is reached
for the first time. The prefix of $\rho_1'$ is then just $\rho_0$.
Let us assume that the next step of $M$ is to the left. We follow the next
steps of $\rho_1$ until either it comes back to position $n+2$ or
until it attempts to step at position 1. If the former happens, this
part of $\rho_1$ is just copied to $\rho'_1$. In the latter case, we
consider for each position $1,\ldots,n-1$ the state $r_i$ in which it
is visited for the first time in the current subrun. Clearly, there must
be $i<j$ with $r_i=r_j$ and we just remove the part of the subrun between
$(j,r_j)$ and $(i,r_i)$. The consideration of the thus shortened run
goes on in this way until position $n+2$ is reached again.
When $M$ moves to the right of $n+2$, a similar procedure is applied with
positions $n+3,\ldots,2n+3$ in place of $1,\ldots,n+1$.
It is easy to see (but a bit tedious to formally denote) that the resulting subrun
$\rho'_1$ is valid for $M$, remains in the interval $[2,\ldots,2n+2]$
and eventually reaches state $q$ at some position $k$. It is then
extended to an accepting run as described above.
