Sea también
el conjunto de estados accesibles en la gráfica de transición mediante
partiendo del estado inicial.
Una palabra
es reconocida por la gráfica de transición
si para alguna palabra
tal que
,
se tiene que
es reconocida por el autómata no-determinista
.
El lenguaje de la gráfica está formado por todas las palabras que reconoce.
Observación 4.1
Las siguientes dos relaciones se cumplen:
.
.
Un lenguaje
se dice regular-G si existe una gráfica de transición
sobre el alfabeto
tal que
.
Todo autómata no-determinista sin transiciones-
es una gráfica de transición. Por tanto, todo lenguaje regular-N es también regular-G.
En cuanto al recíproco, se puede ver inmediatamente que todo lenguaje regular-G en el diccionario
es regular-N en el diccionario
y, debido al lema 3.3.2, es de hecho regular en ese mismo diccionario. Así pues, toda gráfica de transición es equivalente a un autómata finito con transiciones-.
Sin embargo, con esta construcción se ha aumentado un símbolo al alfabeto. Veamos que se puede eliminar de manera equivalente a las transiciones-.
Lema 4.1 (Equivalencia de GT's y AF's)
Todo lenguaje regular-G es regular.
Es decir, para cada gráfica de transición
sobre el alfabeto
existe un autómata finito
sobre el alfabeto
tal que
.
En efecto, para construir un autómata finito equivalente a una gráfica de transición dada, se puede seguir cualquiera de las dos construcciones presentadas en el lema 3.3.2 partiendo del correspondiente autómata no-determinista, sólo que en vez de considerar las relaciones
se considerará las relaciones
.
También, para evitar considerar estados irrelevantes se puede ``filtrar'' la segunda construcción con el algoritmo (3.5) de cálculo de partes accesibles.
Presentamos un seudocódigo de este procedimiento en la figura (3.7). Si
es el conjunto de estados de la gráfica, la lista
denota al subconjunto Q' tal que para todo j,
.
El nuevo estado final es la mónada que consiste del estado inicial q0,
.
Figure 3.7:
Conversión de una gráfica de transición a un autómata finito equivalente.
Los estados finales serán todos aquellos nuevos estados que incluyan alguno final de los viejos estados.
Ejemplo. Sea
la gráfica de transición definida como sigue:
estados:
,
entradas:
,
estado inicial:
q0=0,
estados finales:
,
transición:
.
La palabra
realiza la transición 01221330 y consecuentemente la palabra 1001 es reconocida. Una palabra que consista sólo de 1's no puede ser reconocida.
Se puede ver que ``partir del estado 0'' es como si se ``partiera del estado 1 o del estado 2'' pues a ambos se llega desde el estado 0 con palabras de la forma .
Por la misma razón, si se arriba al estado 0 se arriba también a los estados 1 y 2, si se arriba al estado 1 se arriba también al estado 2 y si se arriba al estado 3 se arriba también a los estados 0, 1, 2.
Al aplicar el algoritmo (3.7) obtenemos la tabla siguiente:
El estado inicial del autómata equivalente consiste de la mónada formada por el estado 0, es pues 1000, y los estados finales son los que tienen prendido el ``bit'' de la extrema izquierda, a saber 1000 y 1111.
Siguiente:Autómatas bidireccionalesUn nivel arriba:Gráficas de transición Anterior:Nociones básicasGuillermo Morales-Luna
2000-06-27