Autómata finito determinista

Dificultad

Fácil 25%

contenido

Estamos acostumbrados a dibujar un autómata finito determinista, representando los estados mediante círculos, indicando el estado inicial mediante una flecha entrante, los estados de aceptación mediante un círculo doble o una flecha saliente, y la transición del estado q al estado q' leyendo la letra α mediante una flecha yendo de q a q' y etiquetados por α.

Un autómata finito determinista A es un triplete (Vt, Q, T) donde

Vt es el vocabulario del autómata;
Q es el conjunto finito de estados del autómata;
T: Q × Vt → Q, es una aplicación parcial llamada función de transición del autómata.

Cuando T es total, en otras palabras, si en cada estado hay exactamente una transición para cualquier letra del alfabeto, se dice que el autómata está completo.

Leyendo una palabra

Nótese que la derivación que produce la lectura de una palabra w por un autómata finito determinista es lineal y, por tanto, está libre de ambigüedad: la lectura de las letras que componen la palabra provoca transiciones bien definidas hasta que se bloquea en caso de transiciones. , o hasta llegar a cierto estado tras la lectura completa de la palabra. Para comprobar la lectura de una palabra, es necesario partir de los estados iniciales y consumir los símbolos uno a uno mientras se avanza en el PLC hasta que se tenga un caso imposible o la lectura completa de la palabra.

Deducimos la propiedad fundamental de los autómatas deterministas completos:

Sea A = (Vt, Q, T) un autómata finito determinista completo. Entonces, para cualquier palabra u ∈ V^∗_t y cualquier estado q ∈ Q, existe un estado único q '∈ Q tal que q (u) → Aq'.

En la práctica, puede ser útil completar un PLC agregando un nuevo estado llamado basura al que van todas las transiciones que faltan. Los cálculos de bloqueo luego terminan en la papelera donde permanecen capturados.

Un autómata determinista también se puede definir con dos datos adicionales:

de un estado inicial i ∈ Q;
de un conjunto de estados de aceptación F ⊆ Q;

Tenga en cuenta que el estado inicial y los estados de aceptación también se pueden deducir de las reglas T.

Una palabra w es reconocida por el autómata si hay un supuesto cálculo exitoso que resulta del estado inicial i y termina en un estado de aceptación después de haber leído la palabra w. Denotamos por L (A) el lenguaje de palabras reconocido por el autómata A. Se dice que un lenguaje reconocido por un autómata es reconocible. Denotamos por Rec el conjunto de lenguajes reconocibles. Agregar un estado de basura no cambia las palabras reconocidas por un PLC.

Del lenguaje al autómata

Cualquier lenguaje aceptado por un autómata finito es regular. Todo lenguaje normal es aceptado por un autómata finito.

Para cada uno de los idiomas a continuación, explique el idioma y dibuje un autómata determinista que lo reconozca.

L es el idioma denotado por aba + bab.
L es el idioma denotado por (aba)^∗ + (bab)^∗.
L = {u ∈ {a, b}^∗ tal que u contiene el factor bbb}.
L = {u ∈ {a, b}^∗ tal que u no contiene el factor bbb

Podemos transformar efectivamente un gramática regular a la derecha en un autómata finito determinista y viceversa. Los no terminales corresponden a los estados del autómata.

Autómatas con palabras reconocidas

Dé todas las palabras de longitud 0, 1, 2, 3 y 4 reconocidas por los siguientes autómatas. Esta pregunta puede responderse sistemáticamente mediante el uso de matrices. Para ello, representamos al autómata (que podemos ver como un grafico) por la matriz de adyacencia. Así, el coeficiente índice i, j de la matriz M^k corresponde a las palabras de longitud k reconocidas por el PLC, si el estado inicial fue el estado i y el estado final, el estado j. Si deseamos obtener las palabras de longitud k reconocidas por nuestro autómata, basta con multiplicar la matriz por sí misma.

Podemos simbolizar (e incluso almacenar) las transiciones de un autómata finito en forma de una matriz bidimensional. Las líneas representan los estados de inicio de la transición, las columnas indican los símbolos y los valores que los estados de destino de la transición.

Para el autómata A, es suficiente evaluar (1,3) y (1,4) de las siguientes matrices; de hecho, las palabras reconocidas comienzan en el estado 1 y terminan en el estado 3 o 4:

Palabras de longitud 0: ninguna; Palabras de longitud 1: b; Palabras de longitud 2: ab + aa + ba; Palabras de longitud 3: aba + abb + aaa + baa; Palabras de longitud 4: abaa + abab + abba + abbb + aaaa + baaa.