Determinación de AFI a AFD

AFI a AFD

El teorema de Rabin-Scott dice que cualquier idioma reconocido por un autómata finito indeterminista puede ser reconocido por un autómata finito determinista (determinación AFI a AFD). Por lo tanto, es posible representar un autómata indeterminista por un autómata determinista, este proceso se llama determinización.

Considere por ejemplo elautómata finito no determinista (K, T, M, I, F) siguientes:
K = {S1, S2, S3, S4}
T = {a, b, c}
M = {(S1, a, S1), (S1, a, S3), (S2, b, S2), (S2, b, S3), (S3, c, S3), (S3, c, S4) }
I = {S1, S2}
F = {S4}
correspondiente a grafico Próximo :

Luego construimos los estados del autómata finito determinista (AFD) y su función de transición. Al principio, tiene un solo estado que se compone del conjunto de estados iniciales del autómata finito indeterminista (AFI): en nuestro ejemplo, el estado inicial de AFD es {S1, S2}.

Cada vez que agregamos un nuevo estado en el AFD, determinamos su función de transición haciendo la unión de las líneas correspondientes en la tabla de transición de
AFI: en nuestro ejemplo, para el estado {S1, S2}, hacemos la unión de las líneas correspondientes a S1 y S2, y determinamos la función de transición

En otras palabras, cuando estamos en el estado "S1 o S2" y leemos una a, vamos al estado "S1 o S3" (M ({S1, S2}, a) = {S1, S3}), cuando están en el estado "S1 o S2" y leemos ab, vamos al estado "S2 o S3" (M ({S1, S2}, b) = {S2, S3}) y cuando estamos en el estado "S1 o S2" y leemos ac, pasamos al estado "vacío", correspondiente al estado de error (M ({S1, S2}, c) = ∅.

Los estados {S1, S3} y {S2, S3} se agregan luego al AFD y su función de transición se determina de acuerdo con el mismo principio. Poco a poco, construimos la siguiente tabla de transición para AFD:

El conjunto de estados AFD es K '= {{S1, S2}, {S1, S3}, {S2, S3}, {S3, S4}}. Los estados AFD que contienen un estado final AFI son estados finales. Aquí, AFI tiene un solo estado final S4 y el conjunto de estados finales de AFD es F '= {{S3, S4}}. Este AFD corresponde al siguiente gráfico:

Otro ejemplo

Aquí hay otro ejemplo de determinación de AFI a AFD.

En la práctica, solo construimos los estados accesibles desde I, paso a paso: partimos del estado inicial I, luego calculamos todas las transiciones que parten de I, luego volvemos a comenzar con los nuevos estados obtenidos, etc.

NB: el método del curso también es válido para las tutorías y el proyecto. ¡Usa el que mejor entiendes! Tiene el mismo ejemplo con las notaciones del curso después de este método.

estado inicial: I = {1} transición por a: {1, 2} transición por b: {1}. Acabamos de hacer {1}, así que vamos a hacer {1,2}

estado {1, 2} transición por a: {1, 2} transición por b: {1, 3}, ahora hacemos {1,3}

estado {1, 3} transición por a: {1, 2} transición por b: {1}. No quedan estados sin visitar. Solo el estado {1,3} contiene un estado terminal, por lo que {1,3} es terminal.

Lo que nos da el siguiente DFA:

El cálculo por tablas es mucho más legible.

Calculemos los estados delta prime:

La segunda línea crea el estado {1,3} para nosotros. Observamos que al final, el autómata es el mismo que el calculado con el método anterior (el estado 3 no sirve ya que nadie lo llama).