TEOREMA DE TRANSFORMACIÓN AFN A AFD


TEOREMA DE TRANSFORMACIÓN AFN A AFD
Ricardo A. Villagrán us

Para todo AFN N existe algún AFD tal que L(N)=L(D)

Un AFN con transiciones  puede ser convertido en un AFN sin transiciones , eliminando las transiciones vacías, sin alterar el comportamiento del autómata. Para hacer esto, es necesario comprender que las deltas manejadas tienen una diferencia cuando se trata de la cerraduraal vacío, ya que en el AFN sin  la cerradura al vacío de un estado es solamente el mismo estado.


LEMA:

Para cada x,y   y A  K, (A,xy) = ((A,x),y)
El lema anterior nos dice que es posible separar las cadenas en una operación de transición de un Autómata Finito. Esta separación nos ayudará a simplificar el rastreo de la cadena general.


EJERCICIOS:

Obtener un AF que acepte((a+b)(a+b))*(ab+(ba)*)
Obtener una ER para el lenguaje generado por el siguiente autómata:


La de Expresión Regular y su relación para ser representado por un Autómata Finito.




La construcción de AF’s tiene como base los grafos de transición, los cuales nos muestran cómo un lenguaje puede ser reconocido por dicho grafo.

NOCIONES BÁSICAS
Los autómatas no-deterministas seconforman como los autómatas finitos ya vistos, salvo que sus transiciones, en lugar de ser funciones, son relaciones que a cada pareja (estado, estímulo) le asocian varios, uno o ningún estado. Más precisamente:


Un semiautómata no-determinista es una estructura de la forma

donde


Un autómata no-determinista es una pareja donde SAFND es un semiautómata no-determinista y es un conjunto deestados finales. Si decimos que se puede transitar a p desde el estado q cuando arriba un símbolo e. Para cada pareja su imagen bajo la transición es el conjunto , es decir, es el conjunto de estados a los que se puede transitar desde q con e. De manera reiterada, para , definimos la imagen como sigue:



Para cada definimos .

Una palabra es reconocida por el autómata si algún estado en esfinal. El lenguaje del autómata consiste de todas las palabras que reconoce,

Ejemplo. Sea el autómata no-determinista tal que


En la siguiente tabla presentamos el cálculo de la correspondiente función T en algunas palabras:



Así pues, y consecuentemente .


  NOTA:

Todo autómata finito (determinista) es también un autómata finito no-determinista.

En efecto, lasfunciones son casos particulares de relaciones. Por tanto, toda función de transición, es una relación de transición





.





INDETERMINISMO Y DETERMINISMO
Diremos que un lenguaje es regular-N si coincide con el lenguaje reconocido por algún autómata no-determinista. Ya que todo autómata finito es en sí mismo un autómata no-determinista se tiene que todo lenguaje regular es también unlenguaje regular-N. El recíproco también es cierto.

(Equivalencia de determinismo e indeterminismo)   Todo lenguaje regular-N es regular. Es decir, para todo autómata no-determinista existe un autómata finito tal que .
En efecto, sea un autómata no-determinista. Podemos presentar dos construcciones de autómatas finitos equivalentes a .





Primera construcción.

Construyamos elmonoide del autómata no-determinista y consideremos su estructura de autómata finito: cada uno de sus elementos es un estado, para cada símbolo definamos la transición y definamos como estados finales a las clases de equivalencia tales que . Una palabra será reconocida en este último autómata cuando y sólo cuando lo sea por .




Segunda construcción.

Construyamos el autómata finito comosigue:
estados:
Todo subconjunto de estados ``viejos'' será un ``nuevo'' estado,
transición:
Todo subconjunto de estados ``viejos'' se transforma en su imagen bajo la función de transición ``vieja'', , es decir, para cada , si y sólo si .



estado inicial:


Hagamos , la mónada que consta sólo del estado inicial ``viejo''.
estados finales:


Todo subconjunto de estados...