Expresión regular a DFA

Requisito previo : introducción de autómatas finitos

Utilidad : para construir DFA a partir de una expresión regular dada, primero podemos construir un NFA para la expresión dada y luego convertir este NFA a DFA mediante un método de construcción de subconjuntos. Pero para evitar este procedimiento de dos pasos, al revés es construir directamente un DFA para la expresión dada.

DFA se refiere a autómatas finitos deterministas. En DFA, para cada estado, y para cada símbolo de entrada, hay uno y solo un estado al que el autómata puede tener una transición desde su estado actual. DFA no acepta ninguna transición ∈.

Para construir un DFA directamente a partir de una expresión regular , debemos seguir los pasos que se enumeran a continuación:

Ejemplo: supongamos que se da una expresión regular r = (a|b)*abb

1. Primero, construimos la expresión regular aumentada para la expresión dada. Al concatenar un marcador de extremo derecho único ‘#’ con una expresión regular r, otorgamos el estado de aceptación para la transición ra en ‘#’, lo que lo convierte en un estado importante de la NFA para r#.

So, r' = (a|b)*abb#

2. Luego construimos el árbol de sintaxis para r#.

3. A continuación, debemos evaluar cuatro funciones anulables, firstpos, lastpos y followpos.

1. nullable(n) es verdadero para un Node de árbol de sintaxis n si y solo si la expresión regular representada por n tiene € en su idioma.
2. firstpos(n) proporciona el conjunto de posiciones que pueden coincidir con el primer símbolo de una string generada por la subexpresión arraigada en n.
3. lastpos(n) proporciona el conjunto de posiciones que pueden coincidir con el último símbolo de una string generada por la subexpresión arraigada en n.

Nos referimos a un Node interior como cat-node, or-node o star-node si está etiquetado por una concatenación, | o * operador, respectivamente.

Reglas para calcular nullable, firstpos y lastpos :

Node n	anulable(n)	primera posición (n)	última pos(n)
n es un Node hoja etiquetado como €	verdadero	∅	∅
n es un Node hoja etiquetado con la posición i	falso	{ i }	{ i }
n es un Node or con el hijo izquierdo c1 y el hijo derecho c2	anulable (c1) o anulable (c2)	primerapos(c1) ∪ primerapos(c2)	última posición (c1) ∪ última posición (c2)
n es un Node cat con un hijo izquierdo c1 y un hijo derecho c2	anulable (c1) y anulable (c2)	Si es anulable(c1) entonces primerapos(c1) ∪ primerapos(c2) else primerapos(c1)	Si es anulable(c2) entonces lastpos(c2) ∪ lastpos(c1) else lastpos(c2)
n es un Node en estrella con un Node hijo c1	verdadero	primerapos(c1)	última pos(c1)

Reglas para computar followpos:

1. Si n es un Node gato con hijo izquierdo c1 y hijo derecho c2 e i es una posición en lastpos(c1), entonces todas las posiciones en firstpos(c2) están en followpos(i).

2. Si n es un Node en estrella e i es una posición en lastpos(n), entonces todas las posiciones en firstpos(n) están en followpos(i).

3. Ahora que hemos visto las reglas para calcular firstpos y lastpos, ahora procedemos a calcular los valores de las mismas para el árbol sintáctico de la expresión regular dada (a|b)*abb#.

Ahora calculemos el followpos de abajo hacia arriba para cada Node en el árbol de sintaxis.

NODO	seguir pos
1	{1, 2, 3}
2	{1, 2, 3}
3	{4}
4	{5}
5	{6}
6	∅

4. Ahora construimos Dstates , el conjunto de estados de DFA D y Dtran , la tabla de transición para D. El estado de inicio de DFA D es firstpos(root) y los estados de aceptación son todos aquellos que contienen la posición asociada con el símbolo de marcador final # .

Según nuestro ejemplo, la primera posición de la raíz es {1, 2, 3}. Sea este estado A y considere el símbolo de entrada a. Las posiciones 1 y 3 son para a, así que B = seguirpos(1) ∪ seguirpos(3) = {1, 2, 3, 4}. Como este conjunto aún no se ha visto, establecemos Dtran[A, a] := B.

Cuando consideramos la entrada b, encontramos que de las posiciones en A, solo 2 está asociado con b, por lo que consideramos el conjunto followpos(2) = {1, 2, 3}. Como este conjunto ya se ha visto antes, no lo añadimos a Dstates sino que añadimos la transición Dtran[A, b]:= A.

Continuando así con el resto de los estados, llegamos a la siguiente tabla de transición.

	Aporte
Estado	a	b
⇢ Un	B	A
B	B	C
C	B	D
D	B	A

Aquí, A es el estado de inicio y D es el estado de aceptación.

5. Finalmente dibujamos el DFA para la tabla de transición anterior.

El DFA final será: