Autómata finito determinista
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 las derivaciones producidas por la lectura de una palabra w por un autómata finito determinista es lineal y por lo tanto libre de ambigüedad: la lectura de las letras que componen la palabra provoca transiciones bien definidas hasta bloquearse en caso de falta de transiciones, o hasta llegar a un cierto estado tras la lectura completa de la palabra. Para verificar la lectura de una palabra, es necesario partir de los estados iniciales y consumir los símbolos uno a uno mientras se mueve en el autómata hasta tener 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 único estado 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 llamado cálculo exitoso que viene del estado inicial i y termina en el estado de aceptación después de haber leído la palabra w. Denotamos por L(A) el lenguaje de las palabras reconocidas 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 basura no cambia las palabras reconocidas por un autómata.
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 Mk 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, basta con 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.
