Autómata finito

Un autómata finito (en inglés, finite state machine o finite automaton) es un modelo de computación de un ordenador primitivo, formado por varios estados y varias transiciones, que es capaz de aceptar o rechazar una palabra dada.

Ejemplo

Describiremos de manera informal un autómata finito mediante un diagrama de estados que lo representa:

El autómata está formado por estados; en la figura son los tres estados redondos q₀, q₁ y q₂. Entre estos estados hay transiciones, que son las flechas. Además, en el autómata debe haber un estado inicial, que es el estado q₀. El estado inicial suele representarse con una flecha que llega a él sin salir de ningún estado. Por lo general, el autómata tiene también un estado final, que representamos con una línea doble; en la figura es el estado q₂.

Un autómata construido así acepta ciertas palabras. Introducimos palabras en el autómata y este intenta aceptarlas. Si las acepta, el autómata responde SÍ; si no las acepta, responde NO. Nuestro autómata intenta aceptar palabras formadas por las letras «a, b, c», así que podemos probar con la palabra «abbc».

Empezamos en el estado inicial q₀ y en la entrada está la palabra «abbc». A partir de ahí nos guiaremos por las flechas.

Recorremos la palabra de la manera habitual, de izquierda a derecha, es decir, el primer símbolo que tomamos es «a». La flecha para la entrada «a» va al estado q₁, así que pasamos a él y eliminamos el símbolo «a» de la palabra. En la entrada queda la palabra «bbc»:

La flecha para la entrada «b» vuelve al nodo q₁. De nuevo eliminamos la primera letra y en la entrada queda la palabra «bc». Seguimos en el estado q₁. Por último, en la entrada queda la palabra «c». Desde el estado q₁, la flecha para la entrada «c» nos lleva al estado q₂.

Ya hemos agotado todas las letras de la palabra de entrada y estamos en el estado q₂, que es un estado final. Por tanto, este autómata finito acepta la palabra «abbc».

Si al final no estuviéramos en un estado de aceptación, el autómata no aceptaría la palabra. Del mismo modo, el autómata no aceptaría la palabra si en algún estado no tuviéramos adónde ir. Por ejemplo, para la entrada «ab» llegaríamos al estado q₁ y allí nos quedaríamos: el autómata no acepta esa palabra. Si probáramos la palabra «aabbc», tampoco tendríamos suerte, porque desde el estado q₁ no sale ninguna flecha para la letra «a».

Así, el autómata finito sirve para reconocer un conjunto de palabras. En la práctica podríamos usar un autómata, por ejemplo, para averiguar si una palabra de entrada dada es un correo electrónico válido.

Definición de autómata finito

Debemos formalizar la idea intuitiva anterior de lo que es un autómata finito, para poder seguir trabajando con los autómatas y hacerlo mejor.

Decimos que un autómata finito (determinista), abreviado AFD, es una quíntupla ⟨Q, Σ, δ, q₀, F⟩, donde

• Q es un conjunto finito de estados,
• Σ (sigma mayúscula) es el alfabeto (un conjunto finito de símbolos o letras),
• δ: Q × Σ ⟶ Q es la función de transición,
• q₀ ∈ Q es el estado inicial,
• F ⊆ Q es el conjunto de estados finales (de aceptación).

Volviendo al autómata anterior,

podemos decir que en el conjunto de estados Q hay tres estados, Q = {q₀, q₁, q₂}. El alfabeto Σ contiene las letras con las que podemos formar las palabras que el autómata aceptará o rechazará. Aquí probablemente será el alfabeto Σ= {a, b, c}, pero puede ser también cualquier superconjunto suyo. El estado inicial q₀ es el estado q₀; ahí no cambia nada. El conjunto de estados finales tiene en este autómata un único estado, F = {q₂}.

Por función de transición entendemos esas tres flechas con letras. Si te confunde la notación δ: Q × Σ ⟶ Q, solo significa que δ es una función (o, mejor dicho, una aplicación) que toma dos parámetros: un estado de Q y una letra de Σ. Al llamar a la función, esta devuelve un nuevo estado. Nuestra función de transición podríamos definirla mediante una tabla así:

$$\begin{array}{ccc}Q& \mathrm{\Sigma }& \to Q\\ q_0& a& q_1\\ q_1& b& q_1\\ q_1& c& q_2\end{array}$$

Si llamamos a δ(q₁, c), aplicamos la tercera fila y la función responde con el estado q₂, igual que el diagrama. Si estamos en el estado q₁ y en la entrada está la letra «c», llegamos al estado q₂. Antes de definir formalmente qué significa que un autómata acepte una palabra, nos apoyaremos en la comprensión intuitiva de este concepto y veremos algunos ejemplos más.

Más ejemplos

1. Construye un autómata que trabaje sobre el alfabeto binario, es decir, Σ= {0, 1}, y que acepte únicamente las palabras que terminan en uno. Por ejemplo, acepta las palabras 1, 01, 000001, 0101011.

   

   Nuestro autómata tiene dos estados: el inicial q₀ y el final q₁. Siempre que en la entrada aparece la cifra 1, pasamos al estado final q₁ y nos quedamos en él. En cambio, si en la entrada está la cifra 0, pasamos al estado no final q₀ y también nos quedamos en él.

2. Construye un autómata sobre el alfabeto binario que acepte únicamente las palabras cuya letra inicial sea distinta de la letra final.

   

   El autómata se divide ya en el primer paso en dos «subautómatas». Si la palabra empieza por cero, el autómata entra en la parte izquierda y ya se queda allí; si empieza por uno, pasa a la parte derecha. Después ya es lo de siempre: si estamos en la parte izquierda y en la entrada hay un 1, pasamos al estado final y ya nos quedamos allí. Si en la entrada hay un 0, pasamos al estado q₁, que no es final.

   A diferencia de los autómatas anteriores, este autómata tiene varios estados finales, es decir, F = {q₃, q₄}.

3. Construye un autómata sobre el alfabeto binario que acepte únicamente las palabras que no contengan dos ceros seguidos.

   

   Este autómata es interesante por dos razones. La primera es que acepta la palabra vacía. Podemos intentar introducir la palabra vacía en el autómata y este la aceptará si el estado inicial es a la vez un estado final, que es lo que ocurre en este autómata. Como la palabra vacía es una palabra que no contiene dos ceros seguidos, eso es lo correcto. Otra particularidad es que todos los estados de este autómata son finales. El único caso en que el autómata no aceptaría una palabra es cuando desde un estado no saliera ninguna transición. Eso ocurre en el estado q₁, que no tiene transición para 0, porque entonces la palabra contendría dos ceros seguidos.

4. Construye un autómata sobre el alfabeto {-,+,.,0,1,…,9} que acepte únicamente las palabras que representen un número. Es decir, o bien un número entero, como 2, 548, 98263, o bien un número decimal escrito con punto, como 5584.48, 3.14, y ambos también en su versión negativa con el signo menos -2, -548, -3.14, e incluso con el signo más escrito explícitamente, es decir, +2, +548, +3.14. Además, debemos poder escribir el número 0.123 simplemente como .123 (sin ese cero del principio), también con ambos signos. Introduciremos una notación auxiliar: en lugar de escribir diez transiciones para las diez cifras, usaremos el símbolo N.

   

5. Construye un autómata sobre el alfabeto binario que acepte únicamente las palabras de la forma 0ⁿ1ⁿ, lo que significa que las palabras tienen al principio cierto número de ceros y a continuación el mismo número de unos. Ejemplos de tales palabras son 0011, 00001111, 01.

   Un autómata así no se puede construir, porque no somos capaces de «recordar» en ningún sitio el número de ceros. Tendríamos que crear varios «subautómatas», como en el segundo ejemplo, pero haría falta una cantidad infinita de «subautómatas», uno para cada valor de n.

Formalización del cómputo del autómata

Ya hemos definido formalmente el propio autómata finito. Ahora debemos definir además qué hace en realidad un autómata así, es decir, definiremos el cómputo del autómata.

Configuración del autómata: decimos que un par ⟨q, w⟩ ∈ Q × Σ^∗ es una configuración del autómata, donde q es el estado actual en el que se encuentra el autómata y w es la parte de la palabra que aún no se ha leído. Σ^∗ denota la clausura de Kleene del alfabeto Σ, el conjunto de todas las palabras que se pueden formar con las letras del alfabeto Σ. La clausura incluye también la palabra vacía, que denotamos ε.

Si tenemos un autómata ⟨Q, Σ, δ, q₀, F⟩ y tratamos de aceptar la palabra w, el autómata se encuentra en la configuración inicial ⟨q₀, w⟩. Si volvemos al autómata

y queremos aceptar la palabra w = abbc, la configuración inicial será ⟨q₀, abbc⟩.

El paso de cómputo lo definimos como una relación ↦ entre los conjuntos (Q × Σ^∗) × (Q × Σ^∗), es decir, entre configuraciones del autómata. Sea w = w₀w₁… w_n la parte aún no leída de la palabra w. Entonces decimos que los pares ⟨q₁, w₀w₁… w_n⟩ y ⟨q₂, w₁… w_n⟩ están en la relación ↦, lo que escribimos como

$$⟨q_1,w_0{w}_1\dots w_n⟩\mapsto ⟨q_2,w_1\dots w_n⟩,$$

si y solo si δ(q₁, w₀) = q₂. Volviendo a nuestro ejemplo, la configuración inicial es ⟨q₀, abbc⟩. En el diagrama vemos que para la entrada «a» podemos avanzar al estado q₁. Así podemos escribir

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩,$$

porque se cumple δ(q₀, a) = q₁. Con ello hemos realizado un paso de cómputo: hemos mirado a qué estado deberíamos ir para la entrada dada (= la primera letra de la parte aún no leída de la palabra), hemos pasado a él y hemos eliminado la primera letra de la parte no leída de la palabra. Así hemos obtenido una nueva configuración.

La clausura reflexiva y transitiva de la relación paso de cómputo se denota ↦ ^∗. Si escribimos K₁ ↦ ^∗ K₂, donde K₁, K₂ son configuraciones del autómata, significa que desde la configuración K₁ podemos llegar, tras varios pasos de cómputo, a la configuración K₂; es decir, existe una sucesión finita de configuraciones tal que:

$$K_1\mapsto K_{11}\mapsto K_{12}\mapsto K_{13}\mapsto \cdots \mapsto K_2$$

Por ejemplo, en nuestro autómata se cumple ⟨q₀, abbc⟩ ↦ ^∗ ⟨q₁,bc⟩, porque si realizamos dos pasos de cómputo, nos queda la palabra «bc» y permanecemos en el estado q₁. Es decir, existe esta sucesión de configuraciones:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩$$

El autómata acepta la palabra w si y solo si existe un q_f ∈ F tal que $$⟨q_0,w⟩{\mapsto }^{\ast }⟨q_f,\epsilon ⟩$$ Esto significa que el autómata acepta la palabra w si y solo si existe una sucesión de pasos de cómputo tal que, al final de esa sucesión, hemos leído la palabra entera y nos encontramos en un estado final del autómata. El hecho de que hayamos leído la palabra entera se expresa porque en la configuración, en el lugar de la palabra, está ε, la palabra vacía. Nuestro autómata acepta la palabra abbc, porque existe esta sucesión de configuraciones:

$$⟨q_0,abbc⟩\mapsto ⟨q_1,bbc⟩\mapsto ⟨q_1,bc⟩\mapsto ⟨q_1,c⟩\mapsto ⟨q_2,\epsilon ⟩$$

y el estado q₂ es un estado final, q₂ ∈ F.

El lenguaje aceptado por un autómata es el conjunto de todas las palabras que el autómata acepta. El lenguaje del autómata A lo denotaremos L(A). Se cumple, por tanto, que L(A) ⊆ Σ^∗ y

$$L(A)=\{w\in {\mathrm{\Sigma }}^{\ast }\mid A\text{ acepta la palabra }w\}$$

Un lenguaje regular es un lenguaje que es aceptado por algún autómata finito.

Dos autómatas finitos son equivalentes si aceptan el mismo lenguaje. Es decir, los autómatas A₁ y A₂ son equivalentes si se cumple L(A₁) = L(A₂).

Fuentes

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools