En esta sección, discutiremos el método de convertir NFA a su equivalente DFA. En NFA, cuando se proporciona una entrada específica al estado actual, la máquina pasa a varios estados. Puede tener cero, uno o más movimientos en un símbolo de entrada determinado. Por otro lado, en DFA, cuando se proporciona una entrada específica al estado actual, la máquina pasa a un solo estado. DFA solo tiene un movimiento en un símbolo de entrada determinado.
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: En Q', encuentre el posible conjunto de estados para cada símbolo de entrada. Si este conjunto de estados no está en Q', entonces agréguelo a Q'.
hacer bucle while en java
Etapa 4: En DFA, el estado final serán todos los estados que contengan F (estados finales de NFA)
Ejemplo 1:
Convierta el NFA dado a DFA.
Solución: Para el diagrama de transición dado, primero construiremos la tabla de transición.
| Estado | 0 | 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | {q1, q2} | q1 |
| *q2 | q2 | {q1, q2} |
Ahora obtendremos la transición δ' para el estado q0.
punto numeroso
δ'([q0], 0) = [q0] δ'([q0], 1) = [q1]
La transición δ' para el estado q1 se obtiene como:
δ'([q1], 0) = [q1, q2] (new state generated) δ'([q1], 1) = [q1]
La transición δ' para el estado q2 se obtiene como:
δ'([q2], 0) = [q2] δ'([q2], 1) = [q1, q2]
Ahora obtendremos la transición δ' en [q1, q2].
δ'([q1, q2], 0) = δ(q1, 0) ∪ δ(q2, 0) = {q1, q2} ∪ {q2} = [q1, q2] δ'([q1, q2], 1) = δ(q1, 1) ∪ δ(q2, 1) = {q1} ∪ {q1, q2} = {q1, q2} = [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 será:
Arquitectura de 32 bits frente a 64 bits
| Estado | 0 | 1 |
|---|---|---|
| →[q0] | [q0] | [q1] |
| [q1] | [q1, q2] | [q1] |
| *[p2] | [q2] | [q1, q2] |
| *[q1, q2] | [q1, q2] | [q1, q2] |
El diagrama de Transición será:
El estado q2 puede eliminarse porque q2 es un estado inalcanzable.
Ejemplo 2:
Convierta el NFA dado a DFA.
Solución: Para el diagrama de transición dado, primero construiremos la tabla de transición.
repositorio maven
| Estado | 0 | 1 |
|---|---|---|
| →q0 | {q0, q1} | {q1} |
| *q1 | ϕ | {q0, q1} |
Ahora obtendremos la transición δ' para el estado q0.
δ'([q0], 0) = {q0, q1} = [q0, q1] (new state generated) δ'([q0], 1) = {q1} = [q1] La transición δ' para el estado q1 se obtiene como:
δ'([q1], 0) = ϕ δ'([q1], 1) = [q0, q1]
Ahora obtendremos la transición δ' en [q0, q1].
δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0) = {q0, q1} ∪ ϕ = {q0, q1} = [q0, q1] Similarmente,
δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1) = {q1} ∪ {q0, q1} = {q0, q1} = [q0, q1] Como en el NFA dado, q1 es un estado final, luego, en DFA, dondequiera que exista q1, ese estado se convierte en un estado final. Por tanto, en el DFA, los estados finales son [q1] y [q0, q1]. Por tanto conjunto de estados finales F = {[q1], [q0, q1]}.
La tabla de transición para el DFA construido será:
| Estado | 0 | 1 |
|---|---|---|
| →[q0] | [q0, q1] | [q1] |
| *[p1] | ϕ | [q0, q1] |
| *[q0, q1] | [q0, q1] | [q0, q1] |
El diagrama de Transición será:
xd xd significado
Incluso podemos cambiar el nombre de los estados de DFA.
Suponer
A = [q0] B = [q1] C = [q0, q1]
Con estos nuevos nombres el DFA quedará de la siguiente manera:
