# Pumping Lemma over 2 way Automaton

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$?

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."

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.