Secuencia de sincronización

Question

Del libro de Sipser:

Sea $M=(Q,\Sigma,\delta,q_0,A)$ sea un DFA y sea $h$ sea un estado de $M$ llamado su "hogar". A secuencia de sincronización para $M$ y $h$ es una cadena $s\in \Sigma^*$ donde $\delta (q,s)=h$ para cada $q\in Q$ . (En realidad hemos ampliado $\delta$ a cadenas para que $\delta(q,s)$ es igual al estado en el que $M$ termina cuando $M$ comienza en el estado $q$ y lee la entrada $s$ ).

Digamos que $M$ es sincronizable si tiene una secuencia de sincronización para algún estado $h$ .

Demostrar que, si $M$ es un $k$ -DFA sincronizable, entonces tiene una secuencia sincronizadora de longitud máxima $k^3$ . Además, ¿puede mejorar este límite?

Me centro en demostrar la $k^3$ con destino.

Resultados preliminares: El DFA M, dado que es sincronizable, no puede tener más de un estado absorbente y si de hecho tiene uno, el estado "home" no puede ser otro que ese estado absorbente. Pero, ¿cómo puedo demostrar que $k^3$ ¿atado? Mi instinto me dice que utilice la inducción, pero no encuentro una estructura recursiva. Este problema también se publicó en el foro CS hace algún tiempo, pero no obtuve más información de ese debate.

Answer 1

Notación . Sea $|S|$ denotan el número de elementos de un conjunto finito $S$ . Sea $Q$ sea el conjunto de estados del autómata. Dado $S \subseteq Q$ y $u$ una palabra, que $Su = \{ q\cdot u \mid q \in S \}$ .

Sugerencia . Sea $S \subseteq Q$ con $|S| \geqslant 2$ . Demuestre que existe una palabra $u$ de longitud $\leqslant k^2$ tal que $|Su| < |S|$ .