Autómatas que reconocen

Deje ser un alfabeto finito. Un código de sobre es un subconjunto de de tal manera que cada palabra en se puede representar de forma única como una concatenación de palabras en . Un código es finito si es finito ¿Qué se sabe sobre los autómatas (mínimos) que reconocen para un código finito ? ¿Existe alguna caracterización de tales autómatas (en términos de la estructura del autómata, sin conocer )? ¿Es posible, teniendo dicho autómata, extraer el código $\Sigma$ $X$ $\Sigma$ $\Sigma^*$ $X^*$ $X$ $X$ $|X|$ $X^*$ $X$ $X$ $X$ en tiempo polinomial?

También estoy interesado en estas preguntas cuando omitimos el hecho de que es un código, es decir, supongamos solo que es un conjunto finito de palabras. $X$ $X$

automata-theory Andrew Ryzhikov
fuente

¿Qué quieres saber sobre tales autómatas? Parece que es fácil construir un DFA para

cuyo tamaño se pueda caracterizar fácilmente (es básicamente el número de prefijos únicos de cadenas en

, y por lo tanto es la suma de longitudes de palabras en

; en particular, Es de tamaño polinómico). Dado un DFA de este tipo, también parece fácil extraer las palabras de código en

enumerando todos los ciclos desde el nodo de inicio a sí mismo. ¿Cuáles son específicamente tus preguntas? ¿Qué pensamiento has hecho ya? Consulte la sección "Las preguntas deben basarse en ..." de nuestro centro de ayuda .

X^{*}

$X^*$

X

$X$

X

$X$

X

$X$

@DW, obviamente, no todos los autómatas tienen esta propiedad. Entonces, pregunto si hay una caracterización (con suerte, polinomial) de tales autómatas. Además, no veo cómo extraer

enumerando todos los ciclos desde el estado inicial a sí mismo. De hecho, puede haber un número infinito de ciclos, ya que no podemos restringirnos solo a ciclos sin auto intersecciones. ¿Puedes ser más específico por favor?

X

$X$

Andrew Ryzhikov

Si entiendo correctamente, me preguntaste acerca de los autómatas mínimos. Creo que todos los DFA mínimos serán isomorfos al que describí. Si está preguntando acerca de todos los autómatas, no necesariamente mínimos, le sugiero que edite la pregunta para aclararla. No entiendo por qué no se puede restringir solo a los ciclos sin auto intersecciones; la propiedad sin prefijo significa que es seguro hacerlo, y si

es finito, solo habrá muchos ciclos de este tipo. Le sugiero que piense en el problema por un tiempo, luego edite la pregunta para compartir todos los resultados que ha podido llegar hasta ahora.

X

$X$

¿No es esta pregunta la misma que la primera versión de cstheory.stackexchange.com/questions/4284/… , donde

podrían diferir, excepto que también solicita el tiempo de ejecución?

K

$K$

K^{'}

$K'$

domotorp

@domotorp Tienes razón, comprobar si un conjunto de palabras es un código se puede hacer en tiempo polinómico, y es un hecho bastante conocido (ver ej. www-igm.univ-mlv.fr/~berstel/LivreCodes/ Codes.html , subsección 0.4). Lo que quiero es que, teniendo solo un autómata mínimo que reconozca algo, compruebe si este algo es una estrella de un código.

Andrew Ryzhikov

Como esta pregunta no recibió respuesta durante mucho tiempo, permítame ofrecerle una respuesta parcial a la primera parte de la pregunta:

¿Qué se sabe sobre los autómatas (mínimos) que reconocen para un código finito ? $X^∗$ $X$

$X$ $X^*$ $\mathcal{A} = (Q, A, E, I, F)$ $Q = \{1, 1\} \cup \{ (u, v) \in A^+ \times A^+ \mid uv \in X \}$ $I = F = \{(1,1)\}$

\begin{aligned} (u, a v) & \overset{a}{⟶} (u a, v) such that u a v \in X, (u, v) \neq (1, 1) \\ (u, a) & \overset{a}{⟶} (1, 1) such that u a \in X, u \neq 1 \\ (1, 1) & \overset{a}{⟶} (a, v) such that a v \in X, v \neq 1 \\ (1, 1) & \overset{a}{⟶} (1, 1) such that a \in X} \end{aligned}

$\begin{align*} (u, av) &\enspace{\buildrel{a} \over\longrightarrow}\enspace (ua, v) \text{ such that } uav \in X,\ (u, v) \neq (1,1) \\ (u, a) &\enspace{\buildrel{a} \over\longrightarrow}\enspace (1, 1) \text{ such that } ua \in X,\ u \neq 1 \\ (1, 1) &\enspace{\buildrel{a} \over\longrightarrow}\enspace(a, v) \text{ such that } av \in X,\ v \neq 1\\ (1, 1) &\enspace{\buildrel{a} \over\longrightarrow}\enspace (1, 1) \text{ such that } a \in X \bigr\} \end{align*}$

X^{*}

$X^*$

A = {a, b}

$A= \{a, b\}$

X = {a, b a, a a b, a b a}

$X = \{a, ba, aab, aba\}$

X^{*}

$X^*$

$\qquad\qquad\qquad$

$p$ $q$ $w$ $p$ $q$ $w$

$X$ $X^*$

$X$ $A^+$ $A^*$

$R$ $e \in R$ $eRe = \{e\}$ $\pi:R \to S$ $e$ $S$ $\pi^{-1}(e)$

$T$ $X^+$ $X^+$ $T$ $L^+$ $\pi$ $T$ $S$ $X^+$

$\pi:T \to S$

$\mathcal{J}$

Referencias

[ 1 ] J. Berstel, D. Perrin, C. Reutenauer, Códigos y Autómatas . Enciclopedia de las matemáticas y sus aplicaciones, 129. Cambridge University Press, Cambridge, 2010. xiv + 619 pp. ISBN: 978-0-521-88831-8

J.-E. Alfiler
fuente

Autómatas que reconocen

Respuestas: