Automatas finitos deterministas

Capítulo 4

AUTÓMATAS
Por autómata en la matemática discreta entendemos una especie de computadora abstracta
que dada una entrada produce una salida, es decir, calcula alguna función. Generalmente la
entrada es una cadena de símbolos de un alfabeto1, y la salida también, posiblemente sobre
otro alfabeto.
Vamos a estudiar en este capítulo tres clases de autómatas, que se llaman autómatasfinitos,
máquinas secuenciales, y, máquinas de Turing, y después, en el capítulo de lenguajes, máquinas
de pila. Las primeras dos son de memoria finita, y las otras dos de memoria ilimitada pero de
una finita cantidad de información en cualquier momento durante su computación.
Podríamos observar que una computadora electrónica, por mucha memoria RAM y disco
duro que tenga, es un autómata finito, perosí la cantidad de memoria nos permite para la
mayoría de propósitos seguir como si fuera ilimitada. Pero no es nada difícil definir en unas
cuantas líneas una función que agota toda la memoria de cualquier computadora enseguida,
como por ejemplo A(2, 4, 6) (A para Ackermann) donde A(m, p, n) se define así para m, p, n ≥ 0 :
A(m, 0, 0)
A(m, 1, 0)
A(m, p + 2, 0)
A(m, 0, n + 1)
A(m, p + 1, n +1)

=
=
=
=
=

m
0
1
A(m, 0, n) + 1
A(m, p, A(m, p + 1, n)) para todo m, n, p ≥ 0

Aquí p es una operación, digamos opp , y m opp n = m opp−1 m opp−1 m...opp−1 m (n veces). Entonces se puede ver que op0 es adición, op1 es multiplicación, op2 es exponenciación:
m
A(m, 2, n) = mn . op3 es una torre de exponentes, A(m, 3, 3) = mm . En general opp+1 se obtiene de opp en la misma formaque exponención se obtiene de multiplicación y multiplicación de
adición. (Hemos definido A(0, p, 0) = 1, para todo P > 1, mientras 00 por ejemplo queda sin
definición en la matemática, pero nuestro interés es como crece de rápido A.)
Sugerimos que tome unos minutos para programar esto en Maple, a ver que pasa con
A(2, 3, 4). Claro, si lo programamos diciendo que 0 es adición, 1 esmultiplicación y 2 es exponenciación, todas operaciones incorporados a Maple, y vamos a la recursión solo para P > 2
podemos hacer A(2, 3, 4) sin problema (y no presenta demasiada dificultad a mano). A(2, 3, 5)
es algo sorprendente. ¿Y A(2, 3, 6)? ¿A(2, 4, 4)?
Así que conviene ver cuáles son las limitaciones verdaderas de la memoria finita.
Notación. Sea Σ un alfabeto. La cadena vacía se llama ǫ para noconfundirla con el conjunto
vacío ∅ de cadenas. Dadas dos cadenas c1 y c2 , c1 c2 significa la concatenación de las dos. Si
a ∈ Σ, cuando escribimos a puede significar o simplemente la letra a o la cadena de longitud 1
cuya única letra es a, y cuál es será claro del contexto. Por ejemplo, si a ∈ Σ y c es una cadena
sobre Σ, ac significa la concatenación de la cadena a con c. Si C1 y C2 son dosconjuntos de
cadenas, C1 C2 significa el conjunto {c1 c2 : c1 ∈ C1 y c2 ∈ C2 }. Si C es un conjunto de cadenas,
C 0 = {ǫ}, C k+1 = CC k para todo natural k , y C ∗ = ∪∞ C i , es decir, una concatenación de 0
i=0
o más palabras de C . Para una cadena c, con |c| queremos decir la longitud de c.
1Cuando

decimos alfabeto, técnicamente es simplemente un conjunto finito, pero lleva la connotación de quesus miembros son símbolos que son legibles en algún sentido.
63

64

4. AUTÓMATAS

1.

Autómatas finitos y lenguajes regulares

Definición 4.1. Un autómata finito A sobre un alfabeto Σ es (K, Σ, δ, p0 , F ) donde K es un
conjunto finito de estados, δ es una función de K × Σ en K , p0 es un estado (el estado inicial ), y
F es un conjunto de estados (los estados finales ). Extendemos lafunción δ al dominio K × Σ∗ ,
siendo Σ∗ el conjunto de todas las cadenas finitas sobre los símbolos de Σ, diciendo
δ (q, ǫ) = q
Para c en Σ∗ y a en Σ, δ (q, ac) = δ (δ (q, a), c).
El conjunto aceptado por A es {c ∈ Σ∗ : δ (p0 , c) ∈ F }, y se llama C (A).
Definición 4.2. Para un alfabeto Σ, un subconjunto de Σ∗ es regular si es C (A) para algún
autómata A sobre Σ.
Ejemplo 4.3. Sea Σ =...