6
$\begingroup$

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

$\endgroup$
6
+50
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.