[2021] Conversión automática de NFA a DFA {DH}


En esta sección, discutiremos el procedimiento para convertir NFA a su DFA equivalente. Cuando se proporciona una entrada de estado actual específica en NFA, la máquina pasa por diferentes estados. Puede tener cero, uno o más de un sorteo en un símbolo de entrada determinado. Por otro lado, en DFA, la máquina entra en un solo estado cuando se proporciona una entrada específica para el estado actual. DFA solo tiene un sorteo en un símbolo de entrada específico.

Sea M = (Q, ∑, δ, q0, F) un NFA que acepta el lenguaje L(M). Debería haber un DFA equivalente, denotado por M’ = (Q’, ∑’, q0′, δ’, F’) tal que L(M) = L(M’).

Pasos para convertir NFA a DFA:

Paso 1: Inicialmente Q’ = ϕ

Paso 2: Agregue q0 de NFA a Q’. Luego encuentre las transiciones desde este estado inicial.

Paso 3: Encuentre en Q’ el posible conjunto de estados para cada símbolo de entrada. Si este conjunto de estados no está en Q’, agréguelo a Q’.

Paso 4: En DFA, los estados finales son todos los estados que contienen F (estados finales NFA).

Ejemplo 1:

Convierta el NFA proporcionado a DFA.

Conversión de NFA a DFA

Solución: Para el diagrama de transición dado, primero crearemos la tabla de transición.

Condición 0 1
→ q0 q0 q1
q1 {q1, q2} q1
*q2 q2 {q1, q2}

Ahora obtenemos la transición δ’ para el estado q0.

La transición δ’ para el estado q1 se obtiene como:

La transición δ’ para el estado q2 es la siguiente:

Ahora obtenemos la transición δ’ en [q1, q2].

El estado [q1, q2] es también el estado final porque contiene un estado final q2. La tabla de transición para el DFA construido es:

Condición 0 1
→[q0] [q0] [q1]
[q1] [q1, q2] [q1]
*[q2] [q2] [q1, q2]
*[q1, q2] [q1, q2] [q1, q2]

El diagrama de transición será:

Conversión de NFA a DFA

El estado q2 se puede eliminar ya que q2 es un estado inalcanzable.

Ejemplo 2:

Convierta el NFA proporcionado a DFA.

Conversión de NFA a DFA

Solución: Para el diagrama de transición dado, primero crearemos la tabla de transición.

Condición 0 1
→ q0 {q0, q1} {q1}
*q1 ϕ {q0, q1}

Ahora obtenemos la transición δ’ para el estado q0.

La transición δ’ para el estado q1 se obtiene como:

Ahora obtenemos la transición δ’ en [q0, q1].

Similar,

Como en el NFA dado, q1 es un estado final, en DFA, dondequiera que exista q1, ese estado se convierte en un estado final. Por lo tanto, en el DFA son los estados finales [q1] Y [q0, q1]. Por tanto, el conjunto de estados finales F = {[q1], [q0, q1]}.

La tabla de transición para el DFA construido es:

Condición 0 1
→[q0] [q0, q1] [q1]
*[q1] ϕ [q0, q1]
*[q0, q1] [q0, q1] [q0, q1]

El diagrama de transición será:

Conversión de NFA a DFA

Incluso podemos cambiar el nombre de los estados DFA.

Asumir

Con estos nuevos nombres, el DFA se verá así:

Conversión de NFA a DFA






[2021] Conversión automática de NFA a DFA {DH}

Publicaciones Similares

Deja una respuesta

Tu dirección de correo electrónico no será publicada.