Pumping Lemma essentially implies that for a NFA $N$ having $N_0$ states over a unary language $L_0$ any string belonging to $L_0$ can be obtained by 'pumping' one of the strings that have a length smaller than $N_0$. Thus, a string smaller than $N_0$ that is accepted by $N$ always exists. Now, since a 2 Way unary NFA also accepts a regular language, for any 2 way unary NFA $M$ having $M_0$ states over a unary language $L_1$ can we state the same regarding smallest accepted string length (using the same pumping lemma) as above w.r.t. $M_0$?I believe the answer is true, but please confirm?The exact definition of acceptance we are using is the same as provided in the classic (Hopcroft and Ullman - Formal Languages and their relation to Automata, Section 3.7 - Two-Way Finite Automata):A two-way finite automaton will start in state q0 with its input head scanning the leftmost cell on the input tape. Should M ever move off either end of input word x, M halts. An input word will be accepted by M if and only if M eventually moves off the right end of x at the same time it enters a final state.M can reject a word x by:1. moving off the left end of x.2. moving off the right end of x in a nonfinal state.3. looping.
Pumping Lemma over 2 way Automaton
automata theory;regular language
Claim: If $M$ is a 2-way NFA (without endmarkers) with $n$ stateswhich acceptes a unary language $L\not=\emptyset$ then there is a word $w \in L$ oflength at most $3n+5$.Proof sketch:Let $v\in L$ be some word of some length $N>3n+5$ and let $\rho$ bean accepting run for $v$. Let $v=v_1 v_2$, where $v_2$ is the suffixof $v$ of length $n+1$. Let $\rho=\rho_1\rho_2$, where $\rho_1$ isthe prefix of $\rho$ that ends when the head moves from the lastposition of $v_1$ to the right, for the last time. Let $q$ be the laststate of $\rho_1$.Before we manipulate $\rho_1$, we first prepare a way out for $M$ byshowing that we can pump up (!) $\rho_2$.For each of the $n+1$ positions $i$ of $v_2$ let $p_i$ be the firststate in which this position is visited in $\rho_2$. Clearly, theremust 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 tocenter $\rho'_1$ around position $n+2$ and neither let it get toposition 1 nor to position $2n+3$. The construction will make surethat $\rho'_1$ ends in state $q$ at some position (between 2 and 2n+2). Itcan then be completed to an accepting run by adding a suitably pumpedversion 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 reachedfor 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 nextsteps of $\rho_1$ until either it comes back to position $n+2$ oruntil it attempts to step at position 1. If the former happens, thispart of $\rho_1$ is just copied to $\rho'_1$. In the latter case, weconsider for each position $1,\ldots,n-1$ the state $r_i$ in which itis visited for the first time in the current subrun. Clearly, there mustbe $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 rungoes 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 withpositions $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 thenextended to an accepting run as described above.