automata turin

GOBIERNO CONSTITUCIONAL DEL ESTADO LIBRE Y SOBERANO DE OAXACA
INSTITUTO ESTATAL DE EDUCACIÓN PÚBLICA DE OAXACA
COORDINACIÓN GENERAL DE PLANEACIÓN EDUCATIVA
COORDINACIÓN GENERAL DE EDUCACIÓN MEDIASUPERIOR Y SUPERIOR

PROGRAMA DE ESTUDIOS

NOMBRE DE LA ASIGNATURA:
AUTÓMATAS Y LENGUAJES FORMALES

CICLO
CLAVE DE LA ASIGNATURA
TOTAL DE HORAS
CUARTO SEMESTRE
3041
102

OBJETIVOSGENERALES DE LA ASIGNATURA:

Proporcionar al alumno conocimientos fundamentales sobre modelos de máquinas computacionales, sus respectivos lenguajes y gramáticas formales; adquiriendo la capacidad deutilizarlos en el diseño e implementación de aplicaciones reales.

TEMAS Y SUBTEMAS
1. INTRODUCCIÓN.
1.1. Introducción a los autómatas finitos.
1.2. Autómatas y complejidad.
1.3. Conceptoscentrales de la teoría de autómatas.
1.4. Gramáticas formales.

2. AUTÓMATAS FINITOS.
2.1. Definición y propiedades.
2.2. Estructura general.
2.3. Diagramas de transiciones.
2.4. Autómatas finitosdeterministas (AFD).
2.5. Autómatas finitos no deterministas (AFN).
2.6. Autómatas finitos con transiciones épsilon.
2.7. Eliminación de las transiciones épsilon.
2.8. Equivalencias entre AFN y AFD.2.9. Minimización de un AFD.

3. EXPRESIONES Y LENGUAJES REGULARES.
3.1. Minimización de un AFD.
3.2. Autómatas finitos y expresiones regulares.
3.3. Aplicaciones de las expresiones regulares.3.4. Álgebra para las expresiones regulares.
3.5. Lema del bombeo.
3.6. Propiedades de la clausura.

4. GRAMÁTICAS INDEPENDIENTES DEL CONTEXTO.
4.1. Definición y notación.
4.2. Jerarquía deChomsky.
4.3. Derivaciones izquierda y derecha.
4.4. Lenguaje de una gramática.
4.5. Árboles de derivación.
4.6. Aplicaciones de las gramáticas independientes del contexto.
4.7. Ambigüedad en lasgramáticas y lenguajes.
4.8. Gramáticas regulares.

5. AUTÓMATAS DE PILA.
5.1. Definición.
5.2. Notación gráfica.
5.3. Lenguajes aceptados por un autómata de pila.
5.4. Equivalencia entre...