Conversión de NFA a DFA – Part 1

Un NFA puede tener cero, uno o más de un movimiento desde un estado dado en un símbolo de entrada dado. Un NFA también puede tener movimientos NULL (movimientos sin símbolo de entrada). Por otro lado, DFA tiene un solo movimiento desde un estado dado en un símbolo de entrada dado.

Conversión de NFA a DFA
Supongamos que hay un NFA N < Q, ∑, q0, δ, F > que reconoce una lengua L. Entonces se puede construir el DFA D < Q’, ∑, q0, δ’, F’ > para lenguaje L como:
Paso 1: Inicialmente Q’ = ɸ.
Paso 2: Añadir q0 a Q’.
Paso 3: Para cada estado en Q’, encuentre el posible conjunto de estados para cada símbolo de entrada usando la función de transición de NFA. Si este conjunto de estados no está en Q’, agréguelo a Q’.
Paso 4: el estado final de DFA serán todos los estados que contengan F (estados finales de NFA)

Ejemplo
Considere la siguiente NFA que se muestra en la Figura 1.

Los siguientes son los diversos parámetros para la NFA.
Q = { q0, q1, q2 }
∑ = ( a, b )
F = { q2 }
δ (Función de transición de NFA)

Paso 1: Q’ = ɸ
Paso 2: Q’ = {q0}
Paso 3: Para cada estado en Q’, encuentre los estados para cada símbolo de entrada.
Actualmente, el estado en Q’ es q0, encuentre movimientos desde q0 en el símbolo de entrada a y b usando la función de transición de NFA y actualice la tabla de transición de DFA.

δ’ (Función de transición de DFA)

Ahora { q0, q1 } se considerará como un solo estado. Como su entrada no está en Q’, agréguela a Q’.
Entonces Q’ = { q0, { q0, q1 } }

Ahora, los movimientos desde el estado { q0, q1 } en diferentes símbolos de entrada no están presentes en la tabla de transición de DFA, lo calcularemos como:
δ’ ( { q0, q1 }, a ) = δ ( q0, a ) ∪ δ ( q1, a ) = { q0, q1 }
δ’ ( { q0, q1 }, b ) = δ ( q0, b ) ∪ δ ( q1, b ) = { q0, q2 }
Ahora actualizaremos la tabla de transición de DFA .

δ’ (Función de transición de DFA)

Ahora { q0, q2 } se considerará como un solo estado. Como su entrada no está en Q’, agréguela a Q’.
Entonces Q’ = { q0, { q0, q1 }, { q0, q2 } }

Ahora, los movimientos desde el estado {q0, q2} en diferentes símbolos de entrada no están presentes en la tabla de transición de DFA, lo calcularemos como:
δ’ ( { q0, q2 }, a ) = δ ( q0, a ) ∪ δ ( q2, a ) = { q0, q1 }
δ’ ( { q0, q2 }, b ) = δ ( q0, b ) ∪ δ ( q2, b ) = { q0 }
Ahora actualizaremos la tabla de transición de DFA.

δ’ (Función de transición de DFA)

Como no se genera un nuevo estado, hemos terminado con la conversión. El estado final de DFA será el estado que tiene q2 como su componente, es decir, { q0, q2 }

A continuación se muestran los distintos parámetros de DFA.
Q’ = { q0, { q0, q1 }, { q0, q2 } }
∑ = ( a, b )
F = { { q0, q2 } } y la función de transición δ’ como se muestra arriba. El DFA final para el NFA anterior se muestra en la Figura 2.

Nota: A veces, no es fácil convertir una expresión regular a DFA. Primero puede convertir expresiones regulares a NFA y luego NFA a DFA.

Pregunta: El número de estados en el autómata finito determinista mínimo correspondiente a la expresión regular (0 + 1)* (10) es ____________.
Solución: Primero, haremos un NFA para la expresión anterior. Para hacer un NFA para (0 + 1)*, NFA estará en el mismo estado q0 en el símbolo de entrada 0 o 1. Luego, para la concatenación, agregaremos dos movimientos (q0 a q1 para 1 y q1 a q2 para 0) como se muestra en la Figura 3.



Este artículo ha sido aportado por Sonal Tuteja.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.