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
Traté de resolverlo de una manera indirecta:
- Generando una expresión regular
- Haciendo su NFA correspondiente
- Uso de la construcción de conjuntos de potencia para deducir un DFA
- 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:
(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í:
(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
fuente
Respuestas:
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
ba
yab
(que no están en el idioma original, ni el DFA acepta en el paso 3) conducen al estado finalE
.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.
fuente