<p>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$.</p>

<p>Proof sketch:
Let $v\in L$ be some word of some length $N&gt;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$.</p>

<p>Before we manipulate $\rho_1$, we first prepare a "way out" for $M$ by
showing that we can pump up (!) $\rho_2$.</p>

<p>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&lt;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).</p>

<p>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$).</p>

<p>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$.</p>

<p>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&lt;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.</p>

<p>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$.</p>

<p>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.</p>

CC BY-SA 3.0
2017-06-11T02:32:34.677Z
2017-06-11T02:32:34.677Z
Thomas S
<p>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. </p>

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

<p>I believe the answer is true, but please confirm?</p>

<p>The exact definition of acceptance we are using is the same as provided in the classic (<strong>Hopcroft and Ullman - Formal Languages and their relation to Automata, Section 3.7 - Two-Way Finite Automata</strong>):</p>

<p>"<em>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.</em></p>

<p><em>M can reject a word x by:</em></p>

<p><em>1. moving off the left end of x.</em></p>

<p><em>2. moving off the right end of x in a nonfinal state.</em></p>

<p><em>3. looping.</em>"</p>

<automata-theory><regular-language>
Pumping Lemma over 2 way Automaton
TheoryQuest1
# Pumping Lemma over 2 way Automaton

(Asked by: username_0 on 2017-06-06)

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

**Tags:** automata-theory, regular-language


---

## 1 answers

### Answer by username_1 on 2017-06-11. Score: 6 | Accepted answer

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

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

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.


---

