Autómatas Sincronizables Y La Conjetura De Cerný Para Autómatas Aperiódicos

Autómatas sincronizables y la conjetura de Cerný para
autómatas aperiódicos
Pablo Damián Maiuto
Fundamentos de teoría de la computación Universidad Nacional de La Plata, facultad de
informática
La Plata Provincia de Bs As, Argentina
pmaiuto@yahoo.com.ar

Abstract. En esta bibliografía se muestra que es un autómata sincronizable. En
particular, cuales son los últimos resultados en cuantoa la conjetura de Cerný
para autómatas aperiódicos. Se presentan los últimos r esultados demostrados de
la máxima longitud de palabra de reinicio más corta para sincronizar toda clase
de autómata aperiódico y en particular para cuando el grafo subyacente del
autómata aperiódico es fuertemente conexo.

Historia: Autómata sinronizable
Sea A= < Q, ∑, ∂ >, es un Autómata finito deterministico.∑ representa el alfabeto
de entrada, y ∂: Q x ∑  Q es la función de transición que define una acción de las
letras de ∑ en Q. La acción se extiende en forma única a una acción Q x ∑* sobre ∑,
está última acción sigue siendo denotada por ∂.
El autómata A es llamado sincronizable si existe una palabra w ϵ ∑* cuya acción
reinicia A, es decir, deja al autómata A en un estado particular, noimportando en cual
estado de Q se inicio, en ∂(q,w) = ∂(q´,w) para todo q, q´ ϵ Q. Cualquier palabra con
esta propiedad se dice que es una palabra reset (de reinicio).
A continuación se muestra un ejemplo de un autómata sincronizable con 4 estados:

1

a

a, b

1

2

b

b

a

b

3

4
a

Fig. 1. Autómata Sincronizable

Se puede observar de la figura que la palabra abbbabbbareinicia el autómata
llevándolo al estado 2. Con un poco mas de atención y de esfuerzo podemos c hequear
que abbbabbba es la palabra de reinicio más corta para este autómata.
El ejemplo visto en la figura se debe a Jon Cerný cuyo trabajo [1964] introdujo el
concepto de autómata sincronizable por primera vez.
La palabra sincronizable en este contexto fue probablemente introducida porFrederick Hennie, Cerný lo había llamado autómata dirigible, orientable.
Sin embargo, implícitamente, este concepto ha estado presente desde los primeros
días de la teoría de autómatas. El primer autómata sincronizable que apareció en la
literatura apareció en el clásico libro de Ross Ashby´s [1956 pp. 60-61].
Donde Ashby´s trata de domesticar 2 ruidos fantasmales. Cantos y risas en una
mansiónembrujada.
A los fines de este artículo se reproduce la codificación de lo planteado por
Ashby´s, lo que lleva al siguiente autómata.

2

a,c
a

a,c

00

01
01

b,d

c

d

c

d

a

11
b,d

a,c

10
b

Fig. 2 Autómata de Ashby´s

Aquí 00 representa el estado cuando la risa y el canto no se encuentran presentes,
es decir estado silencioso. En los demás estados hayalgún tipo de ruido.
El problema es asegurar el silencio, en otras palabras, llevar el autómata de la
figura al estado 00. Ashby´s solo resuelve el problema ba jo la suposición de que el
autómata esta en el estado 11 y su solución sugerida se codifica por la palabra acb.
Sin embargo es fácil ver que la palabra acb es de hecho una palabra de reinicio (reset)
para el autómata por lo que aplicarla correspondiente secuencia de acciones tendrá la
casa en silencio desde cualquier configuración inicial.
No está claro si Ashby´s noto esta buena característica de su autómata, por otra
parte el hecho de que el autómata de Ashby´s sea sincronizable parece haber sido
pasado por alto por muchos años.

3

La conjetura de Cerný
Ahora se presenta la construcción que realizó Cerný [1964].Para n > 1, Cn representa le autómata finito deterministico cuyos estados son los
residuos de modulo n y cuya entrada son letras a y b, el autóma ta actúa como se
muestra a continuación:
∂(0,a) = 1,
∂(m,a) = m para 0 < m < n;
∂(m,b) = m + 1 (mod n)

0

a

b

a,b
a

n-1

1

b

b

a

n-2

2

a

………
……..

………
……
Fig. 3. El autómata Cn

..

4

Cerný...