Crear Autómata Finito Determinista desde una Expresión Regular

En este post explicaré paso a paso como crear un autómata finito determinista a partir de una expresión regular.

Primero necesitaremos esta tabla para el cálculo de la primerpos y la ultimapos:

Ejemplo:

De la expresión regular crear su autómata finito determinista:

a(bc*)*+a

primero se concatena el símbolo # al final de la expresión regular como delimitador.

a(bc*)*+a#

Ahora al trabajar el árbol sintáctico se debe tener en cuenta la prioridad de los operadores:

1. Paréntesis
2. cerradura de klein (*), cerradura positiva (+)
3. concatenación (.)
4. disyunción (|)

Según estas prioridades se procede a crear el árbol sintáctico de la expresión regular.

y se enumeran los nodos hojas (nodos que no tienen hijos).
Cálculo de anulables, primerapos y ultimapos usando la tabla anterior:

• pp: primerapos
• up: ultimapos

Ahora hallamos la siguientepos(i):

• Si n es un nodo concatenación (.) con hijo izquierdo c1 e hijo derecho c2, e i es una posición dentro de la ultimapos (c1), entonces todas las posiciones de primerapos (c2), están en siguientepos (i).

Los nodos que se encuentran en la ultimapos (up) del hijo izquierdo se le asigna como siguiente pos los nodos que se encuentran en la primerapos (pp) del hijo derecho.

A los nodos 1,2,3 y 4 se le asigna el nodo 5 como siguientepos(i).

• Si n es un nodo asterisco (*), e i es una posición dentro de ultimapos (n), entonces todas las posiciones de primerapos(n) están en siguientepos (i).

Los nodos que se encuentran en la ultimapos (up) se le asigna como siguiente pos los nodos que se encuentran en la primerapos (pp).

A los nodos 2 y 3 se le asigna como siguientepos(i) el nodo 3.

Ahora se procede a construir las transiciones y el conjunto de estados para D.

1. Se procede a construir estadosD, tranD y la tabla de transiciones para D.
2. Los estados dentro de estadosD son conjuntos de posiciones; inicialmente su estado es "no marcado", y cambia a "marcado" justo antes de considerar sus transiciones de salida.
3. El estado inicial de D es primerapos de la raiz.
4. Los estados de aceptación son todos los estados que contengan asociado el delimitador '#'.

Empezamos con el estado de inicio:
primerapos(raiz)={1,4}
Creamos un conjunto A

Para cada símbolo del alfabeto (a,b,c)
Ahora vemos
tranD[A,a]={1,4}
tranD[A,a]=siguientepos(1) U siguientepos(4)
tranD[A,a]={2,5}...(Conjunto no existe, por lo que se crea el conjunto B={2,5})
tranD[A,a]=B

tranD[A,b]={}
tranD[A,c]={}
(Como el conjunto A ya leyó todos los símbolos cambia el estado de su marca)
tranD[B,a]={}
tranD[B,b]={2}
tranD[B,b]=siguientepos(2)
tranD[B,b]={2,3,5}...(Conjunto no existe, por lo que se crea el conjunto C={2,3,5})
tranD[B,b]=C

tranD[B,c]={}
(Como el conjunto B ya leyó todos los símbolos cambia el estado de su marca)

tranD[C,a]={}
tranD[C,b]={2}
tranD[C,b]=siguientepos(2)
tranD[C,b]={2,3,5}
tranD[C,b]=C
tranD[C,c]={3}
tranD[C,c]=siguientepos(3)
tranD[C,c]={2,3,5}
tranD[C,c]=C
(Como el conjunto C ya leyó todos los símbolos cambia el estado de su marca)

La tabla de transiciones es:

El autómata para la expesión regular  a(bc*)*+a  sería:

Enlaces relacionados:
Lenguajes Formales