Mates

Breves Notas sobre Aut´matas y Lenguajes o
Jorge L. Ortega Arjona Departamento de Matem´ticas a Facultad de Ciencias, UNAM Octubre 2004

2

´ Indice general
1. Aut´mata Finito o La Caja Negra 2. La Jerarqu´ de Chomsky ıa Cuatro Computadoras 3. Lenguajes Regulares Bombeando Palabras 4. Gram´ticas Generativas a Sistemas Lindenmeyer 5. Aut´matas Celulares o El Juego de la Vida

7

1321

27

35

3

4

Prefacio
Las Breves Notas sobre Aut´matas y Lenguajes introducen en forma simo ple y sencilla a algunos de los temas relevantes en el ´rea de Aut´matas y a o Lenguajes. No tiene la intenci´n de substituir a los diversos libros y publio caciones formales en el ´rea, ni cubrir por completo los cursos relacionados, a sino m´s bien, su objetivo es exponer brevemente yguiar al estudiante a a trav´s de los temas que por su relevancia se consideran esenciales para el e conocimiento b´sico de esta ´rea, desde una perspectiva del estudio de la a a Computaci´n. o Los temas principales que se incluyen en estas notas son: Aut´mata Finio to, la Jerarqu´ de Chomsky, Lenguajes Regulares, Gram´ticas Generativas ıa a y Aut´matas Celulares. Estos temas se exponen haciendo´nfasis en los eleo e mentos que el estudiante (particularmente el estudiante de Computaci´n) o debe aprender en las asignaturas que se imparten como parte de la Licenciatura en Ciencias de la Computaci´n, Facultad de Ciencias, UNAM. o

Jorge L. Ortega Arjona Octubre 2004

5

6

Cap´ ıtulo 1

Aut´mata Finito o La Caja Negra
Ocasionalmente, uno se encuentra con alg´n dispositivo cuyafunci´n u o precisa es incierta o desconocida. En general, si su apariencia no da idea alguna de cu´l es su funci´n, normalmente se nombra a este tipo de dispoa o sitivos como caja negra. Una forma de descubrir c´mo trabaja el dispositivo o es desarmarlo pieza por pieza, y deducir su funci´n mediante an´lisis de sus o a componentes e interconexiones. Esto, sin embargo, no siempre es posible ninecesario. Por otro lado, dado que el dispositivo misterioso normalmente presenta partes tanto de entrada como de salida, es posible descubrir qu´ hace e sin tener que desarmarlo. Imag´ ınese una caja negra particular (figura 1.1) que presenta una terminal el´ctrica marcada como “ENTRADA”, un peque˜o foco etiquetado e n “ACEPTADO”, y un bot´n marcado como “REINICIA”. o

11 00 11 00 11 00

ENTRADA(0.5 o 2.5 V)

REINICIA

ACEPTADO

111 000 111 000 111 000 111 000 111 000

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´s devarios intentos, el foco e repentinamente se enciende: la secuencia ha sido “aceptada”. Tras registrar la secuencia de s´ ımbolos que encendi´ el foco, se repite el experimento, pero o 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´s intenta la misma secuencia, perotras a haber presionado el bot´n de reinicio. El foco se enciende de nuevo. Contio nuando con los experimentos se descubren varias otras secuencias que, tras haber presionado el bot´n de reinicio, tambi´n encienden el foco. Notando o e esto, es interesante preguntarse: ¿hasta d´nde puede llegarse analizando el o comportamiento de la caja negra? Para hacer tal an´lisis, es necesario suponer queel contenido de la caja a se encuentra en alguna clase de equilibrio estable entre una entrada y otra. Tambi´n se supone que el circuito interior de la caja puede encontrarse en e s´lo un n´mero finito de tales estados de equilibrio. Estas suposiciones son o u perfectamente razonables, al menos si se trata de un dispositivo manufacturado. Cuando se describe de la forma anterior, la caja negra es...