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.


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

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.


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.