Autómatas

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, pero sí lacantidad 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 01 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 forma que exponención se obtiene demultiplicació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 es multiplicación y 2 es exponenciación, todasoperaciones 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 no confundirla con el conjunto vacío ∅ decadenas. 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 dos conjuntos 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.
decimos alfabeto, técnicamente es simplemente un conjunto finito, pero lleva la connotación de que sus miembros son símbolos que son legibles en algún sentido.63
1Cuando

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 la función δ al dominio K × Σ∗ , siendo Σ∗ el conjunto detodas 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 Σ = {0, 1}. Sea M = {c ∈ Σ∗ : c representa en binaro un múltiplo de 7}....