Minimización de DFA utilizando el teorema de Myhill-Nerode

Minimización de DFA usando el teorema de Myhill-Nerode:
Se requiere la minimización de DFA para obtener la versión mínima y equivalente de cualquier DFA que consista en el mínimo número de estados posibles. El teorema de Myhill-Nerode se puede utilizar para convertir un DFA en su DFA equivalente con un número mínimo de estados. Este método de minimización también se denomina método de llenado de tablas. También hay otro método llamado Método de partición o Método de equivalencia para la minimización de DFA (visite   https://www.geeksforgeeks.org/minimization-of-dfa/ para obtener información sobre Equivalencia/Método de partición).

Pasos para la minimización de DFA:

1. Cree los pares de todos los estados involucrados en el DFA dado.
2. Marque todos los pares (Q _a , Q _b ) de modo que Q _a   sea el estado final y Qb sea el estado no final.
3. Si hay algún par no marcado (Qa,Qb) tal que δ(Qa,x) y δ(Q _b ,x) estén marcados, entonces marque (Qa,Qb). Aquí x es un símbolo de entrada. Repita este paso hasta que no se puedan hacer más marcas.
4. Combine todos los pares no marcados y conviértalos en un solo estado en el DFA minimizado.

Ejemplo

Considere el siguiente DFA,

La siguiente es la tabla de transición para el DFA anterior

Minimizando el DFA anterior usando el teorema de Myhill-Nerode:

Paso 1: Cree los pares de todos los estados involucrados en DFA.

Paso 2: marque todos los pares (Qa, Qb) de modo que Qa sea el estado final y Qb sea el estado no final.

Paso 3: Si hay algún par no marcado (Qa,Qb) tal que δ(Qa,x) y δ(Qb,x) estén marcados, entonces marque (Qa,Qb). Aquí x es un símbolo de entrada. Repita este paso hasta que no se puedan hacer más marcas.

• Compruebe el par no marcado Q2,Q1
  • Verifique cuando x=0: δ(Q2,0) = Q4 y δ(Q1,0) = Q3, verifique si el par Q4,Q3 está marcado y no, no está marcado.
  • Compruebe cuando x=1: δ(Q2,1) = Q3 y δ(Q1,1) = Q4, compruebe si el par Q4,Q3 está marcado y no, no está marcado.
  • Por lo tanto, no podemos marcar el par Q2,Q1.
• Compruebe el par no marcado Q3,Q0
  • Verifique cuando x=0: δ(Q3,0) = Q5 y ​​δ(Q0,0) = Q1, verifique si el par Q5,Q1 está marcado y no, no está marcado.
  • Compruebe cuando x=1: δ(Q3,1) = Q5 y ​​δ(Q0,1) = Q2, compruebe si el par Q5,Q2 está marcado y no, no está marcado.
  • Por lo tanto, no podemos marcar el par Q3,Q0.
• Compruebe el par no marcado Q4,Q0
  • Verifique cuando x=0: δ(Q4,0) = Q5 y ​​δ(Q0,0) = Q1, verifique si el par Q5,Q1 está marcado y no, no está marcado.
  • Compruebe cuando x=1: δ(Q4,1) = Q5 y ​​δ(Q0,1) = Q2, compruebe si el par Q5,Q2 está marcado y no, no está marcado.
  • Por lo tanto, no podemos marcar el par Q4,Q0.
• Compruebe el par no marcado Q4,Q3
  • Compruebe cuando x=0: δ(Q4,0) = Q5 y ​​δ(Q3,0) = Q5, tal par de estados Q5,Q5 no existe.
  • Compruebe cuando x=1: δ(Q4,1) = Q5 y ​​δ(Q3,1) = Q5, tal par de estados Q5,Q5 no existe.
  • Por lo tanto, no podemos marcar el par Q4, Q3.
• Compruebe el par no marcado Q5,Q1
  • Verifique cuando x=0 : δ(Q5,0) = Q5 y ​​δ(Q1,0) = Q3, verifique si el par Q5,Q3 está marcado y sí está marcado.
  • Por lo tanto podemos marcar el par Q5,Q1.

• Compruebe el par no marcado Q5,Q2
  • Verifique cuando x=0 : δ(Q5,0) = Q5 y ​​δ(Q2,0) = Q4, verifique si el par Q5,Q4 está marcado y sí está marcado.
  • Por lo tanto podemos marcar el par Q5,Q2.

• Hemos verificado todos los pares sin marcar, pero no es necesario detenerse aquí, debemos continuar con este proceso hasta que no se puedan realizar más marcas.
• Compruebe el par no marcado Q2,Q1
  • Verifique cuando x=0: δ(Q2,0) = Q4 y δ(Q1,0) = Q3, verifique si el par Q4,Q3 está marcado y no, no está marcado.
  • Compruebe cuando x=1: δ(Q2,1) = Q3 y δ(Q1,1) = Q4, compruebe si el par Q4,Q3 está marcado y no, no está marcado.
  • Por lo tanto, no podemos marcar el par Q2,Q1.
• Compruebe el par no marcado Q3,Q0
  • Verifique cuando x=0 : δ(Q3,0) = Q5 y ​​δ(Q0,0) = Q1, verifique si el par Q5,Q1 está marcado y sí está marcado.
  • Por lo tanto podemos marcar el par Q3,Q0.

• Compruebe el par no marcado Q4,Q0
  • Verifique cuando x=0 : δ(Q4,0) = Q5 y ​​δ(Q0,0) = Q1, verifique si el par Q5,Q1 está marcado y sí está marcado.
  • Por lo tanto, no podemos marcar el par Q4,Q0.

• Compruebe el par no marcado Q4,Q3
  • Compruebe cuando x=0: δ(Q4,0) = Q5 y ​​δ(Q3,0) = Q5, tal par de estados Q5,Q5 no existe.
  • Compruebe cuando x=1: δ(Q4,1) = Q5 y ​​δ(Q3,1) = Q5, tal par de estados Q5,Q5 no existe.
  • Por lo tanto, no podemos marcar el par Q4, Q3.
• Ahora aunque repitamos el procedimiento no podemos marcar los pares Q2,Q1(ya que Q4,Q3 no está marcado) y Q4,Q3(ya que Q5,Q5 no existe tal par de estados). Por lo tanto, nos detenemos aquí.

Paso 4: Combine todos los pares no marcados y conviértalos en un solo estado en el DFA minimizado.

• Los pares no marcados son Q2, Q1 y Q4, Q3, por lo que los combinamos.

A continuación se muestra el DFA minimizado con Q1Q2 y Q3Q4 como estados combinados.

• Q0 permanece como nuestro estado inicial.
• Q1 y Q2 fueron nuestros estados finales, por lo que incluso si los combinamos, seguirán siendo el estado final combinado.
• Q5 es el otro estado final que tenemos.
• Si comprobamos la tabla de transición original
  • δ(Q0,0) era Q1 y δ(Q1,1) era Q2. A medida que se combinan los estados, la transición de Q0 en las entradas 0 y 1 será al estado Q1Q2.
  • δ(Q1,0) era Q3, δ(Q1,1) era Q4 y δ(Q2,0) era Q4, δ(Q1,1) era Q3. Como los estados se combinan, la transición de Q1Q2 en las entradas 0 y 1 será al estado Q3Q4.
  • δ(Q3,0) era Q5, δ(Q3,1) era Q5 y ​​δ(Q4,0) era Q5, δ(Q4,1) era Q5. Como los estados se combinan, la transición de Q3Q4 en ambas entradas 0 y 1 será al estado Q5.
  • δ(Q5,0) era Q5 y ​​δ(Q5,1) era Q5. Por lo tanto, la transición del estado Q5 en ambas entradas será al propio estado Q5.

Tabla de transición para DFA minimizado