Automatas

Teor´ de Aut´matas y Lenguajes Formales ıa o
Leopoldo Altamirano, Miguel Arias, Jes´s Gonz´lez, Eduardo Morales, u a Gustavo Rodr´ ıguez

Objetivo General
Proporcionar al estudiante los fundamentos de la teor´ de aut´matas as´ ıa o ı como los de lenguajes formales. Tambi´n se incluye una introducci´n a las e o m´quinas de Turing. a Temario 1. Introducci´n o 2. Aut´matas Finitos o 3.Expresiones Regulares y Lenguajes 4. Propiedades de los Lenguajes Regulares 5. Gram´ticas Libres de Contexto y Lenguajes a 6. Aut´mata de Pila o 7. Propiedades de los Lenguajes Libres de Contexto 8. Introducci´n a las M´quinas de Turing o a Modalidad del Proceso de Ense˜anza n El material del curso es impartido por el instructor con resoluci´n de o algunos problemas en clase. Tambi´n se asignarn tareaspr´cticas a los ese a tudiantes cuya soluci´n ser´ en algunos casos discutida en clase. Se tendr´n o a a sesiones de asesor´ con los asistentes de curso. ıa Horario: Clase: Martes 9:30 a 12:00 Jueves 9:30 a 12:00 Martes 12:00 a 13:00 Jueves 12:00 a 13:00 i

Asosoria:

Evaluaci´n: o Tareas 1/3 Examenes Parciales (2) 2/3 1er Parcial 19-Junio-2008 2o Parcial 15-Julio-2008 Calendarizaci´n. o Sem. 12 3 4 5 6 7 8 Fecha 27 y 29 mayo 3 y 5 junio 10 y 12 junio 17 y 19 junio 24 y 26 junio 1 y 3 julio 8 y 10 julio 15 y 17 julio Tema Introducci´n o Aut´matas Finitos o Expresiones Regulares y Lenguajes Props. Lenguajes Regulares (Primer examen) Gram´ticas y Lenguajes Libres de Contexto a Pushdown Automata Props. Lenguajes Libres de Contexto Intro. M´quina de Turing (Segundo examen) a

iiReferencias
1. John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman (2001). Automata Theory, Language and Computation. Addison-Wesley Publishing. 2. Michael Sipser (1997). Introduction to the Theory of Computation. PWS publishing company.

iii

Cap´ ıtulo 1 Introducci´n o
1.1 Teor´ de Aut´matas ıa o

• Estudio de dispositivos o m´quinas de c´mputo abstractas a o o a • Turing en los 30’sestudi´ una m´quina abstracta con las capacidades de las de hoy (en lo que pod´ calcular) ıan • La meta de Turing era describir la frontera entre lo que una m´quina a pod´ hacer y lo que no, su conclusi´n aplica no solo a las m´quinas de ıa o a Turing, sino a las m´quinas actuales a • En los 40’s y 50’s se estudiaron los Aut´matas Finitos o • Finales de los 50’s, N. Chomsky inicia el estudio formal delas gram´ticas a • En 1969 S. Cook extiende el trabajo de Turing para estudiar lo que se pod´ y no calcular (compute), y lo que se pod´ resolver eficientemente ıa ıa o no (NP-duros).

1.2

Introducci´n a Pruebas Formales o

Para qu´ pruebas? e 1

• Hacer hip´tesis inductivas sobre partes de nuestros programas (iteraci´n o o o recursi´n) o – Hip´tesis consistente con la iteraci´n orecursi´n o o o • Entender como trabaja un programa correcto es esencialmente lo mismo que la prueba de teoremas por inducci´n o – Pruebas deductivas (secuencia de pasos justificados) – Pruebas inductivas (pruebas recursivas de un estatuto parametrizado que se usa a s´ mismo con valores m´s bajos del par´metro) ı a a

1.2.1

Pruebas Deductivas

Secuencia de enunciados cuya verdad nos lleva de unenunciado inicil (hip´tesis) o a una conclusi´n. Son del tipo “If H Then C”. o Por ejemplo, probar que: Si x ≥ 4 Entonces 2x ≥ x2 . La idea general es probar que se cumple para 4 y probar que mientras x crece, el lado izquierdo duplica su valor con cada incremento, mientras que el lado derecho crece a una raz´n de ( x+1 )2 . o x Tambi´n existen otras pruebas como pruebas por contradicci´n, por contraeo ejemplos y de conjuntos, pero nos vamos a enfocar en las pruebas por inducci´n. o

1.2.2

Pruebas por Inducci´n o

• Para objetos definidos recursivamente • La mayor´ maneja enteros, pero en aut´matas se trabaja con ´rboles ıa o a y expresiones de varios tipos (expresiones regulares)

2

1.2.2.1

Inducciones estructurales

Probar el enunciado S(X) respecto a una familia de...