En la sección anterior se vió que basta considerar a las máquinas de Moore en el estudio de las propiedades relativas a las máquinas finitas. Más aún, en las máquinas de Moore se puede omitir a la función de respuesta y considerar que en cada estado, el símbolo que se emite al llegar a él es precisamente la etiqueta con que se ``distingue'' a ese estado. Por tanto, si se está interesado en reconocer a todas las palabras que al final emiten un símbolo determinado, bastará con distinguir como finales a los estados que emiten ese símbolo. Las palabras reconocidas son todas aquellas que llegan a los estados finales a partir del estado inicial.
Un autómata finito (determinista) es pues una estructura de la forma
donde
Un semiautómata finito es una estructura de la forma
es decir, es un ``autómata finito'' en el que no se ha especificado estados finales. Todo autómata finito puede ser visto como un semiautómata con estados finales distinguidos. El semiautómata determinado por un autómata se dice ser el semiautómata subyacente del autómata. Todas las nociones y aseveraciones hechas sobre semiautómatas serán válidas también en los autómatas de los que son subyacentes.
Como en las máquinas finitas, ya sea de Mealy o de Moore, en cada semiautómata extendemos la función de transición
a una función
,
haciendo, para cada estado :
Sea
la función
.
Un estado
se dice ser accesible si está en la imagen de T, es decir, si
.
La parte accesible de
es la imagen de T, es decir, consta de todos los estados accesibles a partir del estado inicial.
Lema 2.1
Sea
un semiautómata finito. Cualquier estado accesible se alcanza mediante una palabra de longitud a lo sumo el número total de estados,
.
En otras palabras, la parte accesible del semiautómata coincide con el conjunto
En efecto, para cada
sea
el conjunto de palabras de longitud a lo sumo m. La colección de conjuntos es un recubrimiento (creciente) del diccionario
mediante conjuntos anidados:
Consecuentemente,
es también un recubrimiento de Q mediante conjuntos anidados. Por ser Q finito, necesariamente para algún índice m0 se ha de tener que
,
y, de hecho, para todo ,
.
Así pues, se tiene una cadena finita de inclusiones,
Como cualesquiera dos conjuntos consecutivos
,
pueden diferir en al menos un elemento en Q se tiene que .
Además,
.
De aquí se sigue la tesis del lema, quod erat demonstratum (q.e.d.).
La parte accesible,
,
de un semiautómata
consta de todos sus estados accesibles.
Naturalmente, se tiene un algoritmo elemental para construir la parte accesible de cualquier semiautómata finito:
1.
Consideremos dos listas: una de estados ya revisados y otra de estados por revisar. Inicialmente la primera está vacía y la segunda consta sólo del estado inicial.
2.
Para cada estado por revisar,
(a)
se toma a ese estado como actualq,
(b)
para cada símbolo de entrada
sea
.
Si p aparece en alguna de las dos listas se pasa al siguiente símbolo, en otro caso se lo coloca al final de los estados a revisar,
(c)
se coloca el estado actual en la lista de los ya revisados.
En la figura 3.5 se presenta un seudocódigo de este algoritmo.
Figure 3.5:
Cálculo de la parte accesible.
El lema anterior implica que el número de iteraciones en el ciclo principal del algoritmo anterior no excede al número de estados en el autómata.
Ejemplo.
Si
consta de un único símbolo entonces el algoritmo 3.5 muestra que la parte accesible tiene forma de la letra griega ``rho'', ,
es decir, existen
tales que
Sea
un autómata finito. Decimos que una palabra
es reconocida por A si
,
es decir,
es reconocida si al aplicarla a
desde el estado inicial se arriba a uno de los estados finales.
El lenguaje reconocido por
consta de todas las palabras reconocidas por
:
Diremos que un autómata
subsume a otro autómata
si
.
La relación de ``subsunción'' es reflexiva y transitiva.
Diremos que dos autómatas son equivalentes si uno subsume al otro, es decir, si coinciden los lenguajes reconocidos por ellos. Esta es una relación de equivalencia entre autómatas.
Diremos que un lenguaje
es regular-AF si existe un autómata finito
tal que
.
Ejemplos. Sea
.
1. Construyamos un autómata que reconozca cadenas binarias con números pares de 0's y de 1's. Consideremos los estados siguientes:
La tabla de transición queda definida de manera natural:
El estado inicial es q0 y el conjunto de estados finales es .
Es fácil ver que el lenguaje reconocido por este autómata es
El lenguaje L es pues regular-AF.
En este ejemplo, es también muy fácil ver que para cada
,
queda determinada por las paridades de 0's y de 1's en .
2. Consideremos el autómata con tabla de transición
y estado inicial q0. Observemos que
si se arriba al estado q3 ya no se sale de ahí,
se arriba a q3 si inicialmente aparece un 1 y no hay 0's que lo precedan, o bien, habiendo llegado un bloque de 0's y luego uno de 1's, reaparece un 0.
Así pues, si el conjunto de estados finales es
entonces el lenguaje reconocido por este autómata es
Siguiente:HomomorfismosUn nivel arriba:Autómatas finitos Anterior:Autómatas finitosGuillermo Morales-Luna
2000-06-27