Automatas Y Lenguajes

Breves Notas sobre
Aut´
omatas y Lenguajes
Jorge L. Ortega Arjona
Departamento de Matem´aticas
Facultad de Ciencias, UNAM
Octubre 2004

2

´Indice general
1. Aut´
omata Finito
La Caja Negra

7

2. La Jerarqu´ıa de Chomsky
Cuatro Computadoras

13

3. Lenguajes Regulares
Bombeando Palabras

21

4. Gram´
aticas Generativas
Sistemas Lindenmeyer

27

5. Aut´
omatas Celulares
El Juego de la Vida

353

4

Prefacio
Las Breves Notas sobre Aut´
omatas y Lenguajes introducen en forma simple y sencilla a algunos de los temas relevantes en el ´area de Aut´omatas y
Lenguajes. No tiene la intenci´on de substituir a los diversos libros y publicaciones formales en el ´
area, ni cubrir por completo los cursos relacionados,
sino m´as bien, su objetivo es exponer brevemente y guiar al estudiante atrav´es de los temas que por su relevancia se consideran esenciales para el
conocimiento b´asico de esta ´
area, desde una perspectiva del estudio de la
Computaci´on.
Los temas principales que se incluyen en estas notas son: Aut´omata Finito, la Jerarqu´ıa de Chomsky, Lenguajes Regulares, Gram´aticas Generativas
y Aut´omatas Celulares. Estos temas se exponen haciendo ´enfasis en los elementos que elestudiante (particularmente el estudiante de Computaci´on)
debe aprender en las asignaturas que se imparten como parte de la Licenciatura en Ciencias de la Computaci´on, Facultad de Ciencias, UNAM.

Jorge L. Ortega Arjona
Octubre 2004

5

6

Cap´ıtulo 1

Aut´
omata Finito
La Caja Negra
Ocasionalmente, uno se encuentra con alg´
un dispositivo cuya funci´on
precisa es incierta o desconocida. Engeneral, si su apariencia no da idea
alguna de cu´al es su funci´
on, normalmente se nombra a este tipo de dispositivos como caja negra. Una forma de descubrir c´omo trabaja el dispositivo
es desarmarlo pieza por pieza, y deducir su funci´on mediante an´alisis de sus
componentes e interconexiones. Esto, sin embargo, no siempre es posible ni
necesario. Por otro lado, dado que el dispositivo misteriosonormalmente presenta partes tanto de entrada como de salida, es posible descubrir qu´e hace
sin tener que desarmarlo.
Imag´ınese una caja negra particular (figura 1.1) que presenta una terminal el´ectrica marcada como “ENTRADA”, un peque˜
no foco etiquetado
“ACEPTADO”, y un bot´
on marcado como “REINICIA”.

11
00
00
11
00
11

ENTRADA
(0.5 o 2.5 V)

REINICIA

111
000
000
111
000
111
000
111
000111

ACEPTADO

Figura 1.1: Una caja negra
El dispositivo parece aceptar dos tipos de voltaje, y representando estos con los s´ımbolos 0 y 1, se pueden realizar algunos experimentos dando
7

secuencias de ceros y unos a la caja negra. Al principio, aplicar algunas secuencias parece no afectar al dispositivo. Despu´es de varios intentos, el foco
repentinamente se enciende: la secuencia ha sido“aceptada”. Tras registrar
la secuencia de s´ımbolos que encendi´o el foco, se repite el experimento, pero
la secuencia falla y el foco ya no enciende. En el desconcierto, es posible
comenzar a considerar que el circuito interno de la caja se comporta en forma aleatoria. Entonces, alguien m´as intenta la misma secuencia, pero tras
haber presionado el bot´on de reinicio. El foco se enciende de nuevo.Continuando con los experimentos se descubren varias otras secuencias que, tras
haber presionado el bot´on de reinicio, tambi´en encienden el foco. Notando
esto, es interesante preguntarse: ¿hasta d´onde puede llegarse analizando el
comportamiento de la caja negra?
Para hacer tal an´alisis, es necesario suponer que el contenido de la caja
se encuentra en alguna clase de equilibrio estable entre unaentrada y otra.
Tambi´en se supone que el circuito interior de la caja puede encontrarse en
s´olo un n´
umero finito de tales estados de equilibrio. Estas suposiciones son
perfectamente razonables, al menos si se trata de un dispositivo manufacturado.
Cuando se describe de la forma anterior, la caja negra es esencialmente
un aut´
omata finito. En t´erminos abstractos, este dispositivo consiste...