No se puede convertir de NFA a DFA

11

Tengo un problema simple de hacer un DFA que acepte todas las entradas que comienzan con letras dobles (aa, bb) o terminan con letras dobles (aa, bb), dado que es el conjunto alfabético del lenguaje dadoΣ={a,b}

Traté de resolverlo de una manera indirecta:

  1. Generando una expresión regular
  2. Haciendo su NFA correspondiente
  3. Uso de la construcción de conjuntos de potencia para deducir un DFA
  4. Minimizar el número de estados en DFA

Paso 1: La expresión regular para un problema dado es (entre muchos otros):

((aa|bb)(a|b)*)|((a|b)(a|b)*(aa|bb))

Paso 2: NFA para la expresión dada es:

NFA
(fuente: livefilestore.com )

En forma tabular, NFA es:

State    Input:a     Input:b
->1        2,5         3,5
  2        4           -
  3        -           4
 (4)       4           4
  5        5,7         5,6
  6        -           8
  7        8           -
 (8)       -           -

Paso 3: Convierta en un DFA utilizando la construcción de conjunto de potencia:

Symbol, State       +   Symbol, State (Input:a) +   Symbol, State (Input:b)
   ->A, {1}         |        B, {2,5}           |        C, {3,5}
     B, {2,5}       |        D, {4,5,7}         |        E, {5,6}
     C, {3,5}       |        F, {5,7}           |        G, {4,5,6}
   (D), {4,5,7}     |        H, {4,5,7,8}       |        G, {4,5,6}
     E, {5,6}       |        F, {5,7}           |        I, {5,6,8}
     F, {5,7}       |        J, {5,7,8}         |        E, {5,6}
   (G), {4,5,6}     |        D, {4,5,7}         |        K, {4,5,6,8}
   (H), {4,5,7,8}   |        H, {4,5,7,8}       |        G, {4,5,6}
   (I), {5,6,8}     |        F, {5,7}           |        I, {5,6,8}
   (J), {5,7,8}     |        J, {5,7,8}         |        E, {5,6}
   (K), {4,5,6,8}   +        D, {4,5,7}         +        K, {4,5,6,8}

Paso 4: minimice el DFA:

He cambiado K-> G, J-> F, I-> E primero. En la siguiente iteración, H-> D y E-> F. Por lo tanto, la mesa final es:

  State    +   Input:a     +   Input:b
   ->A     |      B        |      C
     B     |      D        |      E
     C     |      E        |      D
    (D)    |      D        |      D
    (E)    |      E        |      E

Y diagramaticamente se ve así:

DFA final
(fuente: livefilestore.com )

... que no es el DFA requerido! He verificado tres veces mi resultado. Entonces, ¿dónde me equivoqué?

Nota:

  • -> = estado inicial
  • () = estado final
Anurag Kalia
fuente
3
Este es un gran ejemplo para una pregunta básica que se ha planteado bien, porque incluye todo su tren de pensamiento.
Raphael
Se siente genial ser apreciado, gracias! ^^
Anurag Kalia

Respuestas:

5

Está bien hasta el paso 3 (el DFA) pero su minimización es incorrecta.

Está claro que el DFA minimizado no es correcto, porque las entradas bay ab(que no están en el idioma original, ni el DFA acepta en el paso 3) conducen al estado final E.

Mirando sus pasos de minimización, parece que tiene estados finales y no finales unificados; por ejemplo J (final) -> F (no final) e I (final) -> E (no final). Fusionar un estado final con un estado no final cambia el idioma aceptado por el autómata, lo que lleva a la aceptación de cadenas incorrectas como se indicó anteriormente.

rici
fuente
1
Oh. Entonces, eso es lo que está creando un problema aquí. Ahora que lo recuerdo, la última vez que usé este método, ¡no había ningún estado de aceptación en particular en la tabla!
Anurag Kalia