Sitio Web de Héctor E. Medellín Anaya

MATERIA:                 TEORÍA DEL AUTÓMATA
CLAVE:                      E0305
REQUISITOS:            ALGEBRA I
TIPOLOGÍA:              TEÓRICO/PRÁCTICA
ELABORÓ:                HÉCTOR E. MEDELLÍN ANAYA
FECHA:                      1 DE ABRIL DE 1998

PRESENTACIÓN

El curso introduce al alumno en la teoría de lenguajes formales y autómatas. Se hace una breve revisión de la teoría de conjuntos. Se analizan con detalle los lenguajes regulares y los autómatas finitos. Se examinan las gramáticas independientes del contexto y máquinas de Turing. Se analizan los teoremas fundamentales de la teoría de autómatas y lenguajes formales.

OBJETIVO

Explorar la teoría de autómatas y lenguajes formales. Analizar las características de los lenguajes regulares y autómatas finitos. Analizar las características de las gramáticas independientes del contexto y los autómatas de pila. Analizar las Máquinas de Turing y los lenguajes aceptados por ellas. Discutir los teoremas fundamentales de la teoría de autómatas y lenguajes formales.

UNIDAD 1: CONCEPTOS FUNDAMENTALES

OBJETIVO PARTICULAR

En esta unidad se revisan algunos conceptos básicos de la teoría de conjuntos.

1.1. Lógica
1.2. Conjuntos
1.3. Relaciones y funciones
1.4. Inducción
1.5. Cardinalidad

UNIDAD 2: ALFABETOS Y LENGUAJES

OBJETIVO PARTICULAR

Definir los conceptos de alfabeto y lenguaje. Emplear las operaciones con cadenas.

2.1. Alfabetos, palabras y lenguajes
2.2. Operaciones

UNIDAD 3: LENGUAJES REGULARES

OBJETIVO PARTICULAR

Analizar los lenguajes regulares y los autómatas finitos. Examinar las propiedades de los lenguajes regulares. Usar los autómatas finitos como reconocedores de elementos léxicos.

3.1. Lenguajes regulares y expresiones regulares
3.2. Autómata finito determinista
3.3. AFD y lenguajes
3.4. Autómata finito no determinista
3.5. Equivalencia
3.6. e-transiciones
3.7. Autómata finito y expresiones regulares
3.8. Propiedades de los lenguajes regulares

UNIDAD 4: LENGUAJES INDEPENDIENTES DEL CONTEXTO

OBJETIVO PARTICULAR

Analizar las gramáticas regulares. Analizar las gramáticas independientes del contexto. Examinar las propiedades de los lenguajes independientes del contexto. Analizar los autómatas de pila. Demostrar la potencia de las gramáticas independientes del contexto.

4.1. Gramáticas regulares
4.2. Gramáticas regulares y lenguajes regulares
4.3. Gramáticas independientes del contexto
4.4. Árboles de derivación
4.5. Simplificación de gramáticas independientes del contexto
4.6. Propiedades de los lenguajes independientes del contexto
4.7. Autómatas de pila
4.8. Autómatas de pila y lenguajes independientes del contexto
4.9. Forma normal de Greibach

UNIDAD 5: MÁQUINAS DE TURING

OBJETIVO PARTICULAR

Analizar las máquinas de Turing y sus potencialidades. Estimar los límites de la capacidad de cómputo de las máquinas de Turing.

5.1. Definición
5.2. Máquinas de Turing como aceptadoras de lenguajes
5.3. Construcción de máquinas de Turing
5.4. Modificaciones de las máquinas de Turing
5.5. Máquinas de Turing universales

UDIDAD 6: MÁQUINAS DE TURING Y LENGUAJES

OBJETIVO PARTICULAR

Analizar los lenguajes aceptados por las máquinas de Turing. Examinar la jerarquía de lenguajes formales de Chomsky.

6.1. Lenguajes aceptados por máquinas de Turing
6.2. Lenguajes regulares, independientes del contexto, recursivos y recursivamente enumerables
6.3. Lenguajes recursivos y recursivamente enumerables
6.4. Gramáticas no restringidas y Lenguajes recursivamente enumerables
6.5. Lenguajes sensibles al contexto y la jerarquía de Chomsky

Se recomienda que el alumno haya llevado algún curso de demostraciones matemáticas. El material será expuesto por el maestro. Es recomendable el uso de simuladores de autómatas finitos y/o máquinas de Turing y la realización de proyector de programación y/o aplicaciones de la teoría a otras áreas.

EVALUACIÓN

A lo largo del curso los alumnos resolverán problemas de cada tema estudiado. Se hará un examen de cada unidad. Se realizará un pequeño proyecto final sobre alguno de los temas estudiados. La calificación se ponderará de la siguiente forma:

Tareas             50%
Exámenes       30%
Proyectos        20%

TEXTO

Dean Kelley, Teoría de Autómata y Lenguajes Formales. Prentice Hall, 1995.

BIBLIOGRAFÍA

Pedro García, Tomás Pérez, José Ruiz, Encarna Segarra, José M. Sempere, M. Vázquez de Parga. Teoría de Autómata y Lenguajes Formales. Alfaomega, Universidad de Valencia.2001.

Rafael Cases Muñoz, Lluís Màrquez Villodre. Lenguajes, gramáticas y autómatas, curso básico. Alfaomega, UPC. 2002

Algoritmos + Estructuras de Datos = Programas, Niklaus Wirth, Ediciones el Castillo 1980.