Automatización de enrutamiento

Question

Existe una prueba formal de la siguiente pregunta?

Para un DFA $M= (Q,\Sigma,\delta,s,A)$, ampliamos la función de $\delta : Q \times \Sigma^* \to Q$, de tal manera que cada $w \in \Sigma^* $, $\delta(q,w)$ es el individuo $q'$ tal que $(q,w) \to^*M (q',\epsilon)$. Dado un DFA $M= (Q,\Sigma,\delta,s,A)$, podemos decir que una palabra $w \in \Sigma^* $ es de enrutamiento en el autómata $M$ si hay un $q \in Q$ tal que para cada $q' \in Q$ $\delta(q',w) = q$. Un autómata $M$ tener un enrutamiento de la palabra, se llama enrutamiento autómata.

Probar que cada enrutamiento autómata $M$ con $k$ estados tiene un enrutamiento de palabra de longitud en la mayoría de las $k^3$.

Sugerencia: ¿qué se puede decir acerca de la longitud de las palabras de las rutas 2 estados en uno solo?

ACTUALIZACIÓN - creo que si me puede demostrar que no es una palabra w, |w| <= $k^2$ que las rutas 2 estados en uno solo, entonces que se puede construir una cadena de enrutamiento de esta palabra donde la longitud es en la mayoría de las $k^3$

gracias!

Answer 1

Por la sugerencia, supongamos que $q, q^\prime \in Q$ son distintos, y $w \in \Sigma^*$ rutas de $q$ e $q^\prime$ para el mismo estado, es decir, $\delta ( q,w ) = \delta ( q^\prime,w )$. Si $\mathrm{length}(w) > k^2$, considera los pares de la forma $$\langle \delta (q,w_0) , \delta (q^\prime ,w_0 ) \rangle$$ where $w_0$ is an initial segment of $w$ Note that there are only $k^2$ different pairs of states of $M$, and so there are distinct initial segments $w_0 , w_1$ of $w$ such that $$\delta (q,w_0) = \delta (q,w_1) \;\text{and}\;\delta (q^\prime,w_0) = \delta (q^\prime,w_1).$$ Suponiendo que $w_0$ es el menor segmento inicial, podemos escribir $w$ as $w_0 v u$ donde $w_0 v = w_1$. Un simple argumento se muestran ahora que $\delta (q, w_0 u ) = \delta ( q^\prime , w_0 u )$ ($= \delta ( q , w ) = \delta ( q^\prime , w )$).

De ello se sigue que si $q,q^\prime$ son estados enrutable al mismo estado por alguna palabra, entonces no es una palabra de longitud $\leq k^2$ que los testigos de este (y también alcanza el mismo estado final).

---

Ahora supongamos que $M$ es enrutable con estado final $p$. Enumerar los otros estados de la $M$ as $\{ q_1 , \ldots , q_{k-1} \}$. Vamos a construir inductivamente nuestra palabra $w$ como sigue:

• Tenga en cuenta que $q_1 , p$ son enrutables a $p$, y así por lo anterior no es una palabra $w_1$ de la longitud de la $\leq k^2$ tal que $\delta ( q_1 , w_1 ) = \delta ( p , w_1 ) = p$.
• Tenga en cuenta que $q_2^\prime = \delta ( q_2 , w_1 )$ e $p$ son enrutables a $p$, y así por lo anterior no es una palabra $w_2$ de la longitud de la $\leq k^2$ tal que $\delta ( q_2^\prime , w_2 ) = \delta ( p , w_2 ) = p$. Nota, entonces, que el $\delta ( q_2 , w_1 w_2 ) = \delta ( p , w_1 w_2 ) = p$, y también se $\mathrm{length} (w_1 w_2 ) \leq 2 k^2$.
• Continuar de esta manera para todos los otros estados de $M$.