# a version of pumping lemma

I need some assistence with h.w:

Given $L\in L _{reg}$. Prove that there exists an instance $N\in\mathbb{N}$ such that $\forall w \in L$ such that $N\leq |w|$ there exists a division of $w$ for 4 subwords $x, y_1, y_2, z \in \Sigma ^*$ such that $w=xy_1 y_2 z$ and satesfied:

1. $y_1, y_2 \ne \epsilon$

2. $|xy_1y_2|\leq N$

3. $\forall m,n \in \mathbb{N} , xy_1^ny_2^mz\in L$

I managed to show that there exists an $N\in \mathbb{N}$ such that $w\in L, N \leq |w|$, the automata goes over 2 different $q_1, q_2 \in Q$ twice (or a single $q_1 \in Q$ 3 times). I don't know how to devide the string $w$ to setasfied the proof.

Thanks

• I suppose you mean $|w| \geqslant N$. – J.-E. Pin Dec 9 '17 at 23:54
• yes, thanks.... – J. Doe Dec 10 '17 at 17:54

## 1 Answer

Hint. Let $\mathcal{A} = (Q, A, \cdot, q_0, F)$ be minimal DFA of $L$ and let $n = |Q|$. Each word $u = a_1a_2 \dotsm a_k$ of length $k$ of $L$ defines a unique run on $\mathcal{A}$, starting from the initial state $q_0$: $$q_0 \xrightarrow{a_1} q_1 \xrightarrow{a_2} q_2 \ \dotsm \ q_{k-1} \xrightarrow{a_k} q_k \in F$$ It is easy to see that if $k \geqslant n$, one state is visited at least twice. In the same way, prove that if $k \geqslant 2n$, one state $q$ is visited at least three times. This yields a factorisation of the form $u = xy_1y_2z$, with $y_1, y_2$ nonempty and $|xy_1y_2| \leqslant 2n$, for which the run is of the form $$q_0 \xrightarrow{x} q \xrightarrow{y_1} q \xrightarrow{y_2} q \xrightarrow{z} f \in F$$ Conclude.