UNIVERSIDAD DEL ISTMO PROGRAMA DE ESTUDIO 1.-IDENTIFICACIÓN ESCUELA: UNIVERSIDAD DEL ISTMO CLAVE: 3041 TIPO DE ASIGNATURA: TEÓRICA/PRÁCTICA

ASIGNATURA: AUTÓMATAS Y LENGUAJES FORMALES GRADO: ING. EN COMPUTACIÓN, CUARTO SEMESTRE 3033 ANTECEDENTE CURRICULAR:

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

3.- UNIDADES

1. Introducción; 2. Autómatas finitos; 3. Expresiones y lenguajes regulares; 4. Gramáticas independientes del contexto; 5. Autómatas de pila; 6. Propiedades de los lenguajes independientes del contexto; 7. Máquina de turing.

4.- TIEMPO ASIGNADO Y CRÉDITOS DE LA ASIGNATURA. HORAS SEMANA HORAS SEMESTRE CRÉDITOS

TEORÍA PRÁCTICA TOTAL 5 1 6 85 17 102 8

HOJA 1 DE 11

UNIVERSIDAD DEL ISTMO PROGRAMA DE ESTUDIO 5.- CONCENTRADO POR UNIDAD

ASIGNATURA:

UNIDADES

AUTÓMATAS Y LENGUAJES FORMALES

CARGA POR UNIDAD EN HORAS TEORÍA PRÁCTICA TOTAL

OBJETIVOS POR UNIDAD

1. Introducción.

8

0

8

Explicar la importancia de la teoría de autómatas y lenguajes formales en base a sus conceptos centrales

2. Autómatas finitos.

14

4

18

Estudiar las máquinas abstractas más simples de reconocimiento de tokens en su concepción determinista y no determinista

3. Expresiones y lenguajes regulares.

14

4

18

Emplear las expresiones regulares para reconocer o describir los lenguajes aceptados o generados por estas

4. Gramáticas independientes del contexto.

16

3

19

Utilizar las convenciones de notación apropiadas para reconocer o describir lenguajes con reglas inherentemente recursivas

5. Autómatas de pila.

13

3

16

Estudiar la relación y aplicación de los autómatas de pila respecto a las gramáticas independientes del contexto

6. Propiedades de los lenguajes independientes del contexto.

12

0

12

Identificar los lenguajes libres de contexto mediante el estudio de sus propiedades

7. Máquina de turing.

8

3

11

Identificar la importancia y aplicaciones de la máquina de turing

HOJA 2 DE 11

UNIVERSIDAD DEL ISTMO PROGRAMA DE ESTUDIO

6.- PROGRAMA DE ESTUDIOS ASIGNATURA: AUTÓMATAS Y LENGUAJES FORMALES UNIDAD: 1. Introducción.

TEMA

OBJETIVO: Explicar la importancia de la teoría de autómatas y lenguajes formales en base a sus conceptos centrales

HORAS

1.1. Introducción a los autómatas finitos.

2

1.2. Autómatas y complejidad.

2

1.3. Conceptos centrales de la teoría de autómatas.

2

1.4. Gramáticas formales.

2

ACTIVIDADES DE APRENDIZAJE Investigar en fuentes bibliográficas cada tema Resolver ejercicios y problemas sencillos

TÉCNICAS

APOYOS DIDÁCTICOS

Exposición y debate de temas en salón de clase.

Proyector, Computadora personal, diapositivas pizarrón

Desarrollo de ejemplos y ejercicios ilustrativos

libros

HOJA 3 DE 11

UNIVERSIDAD DEL ISTMO PROGRAMA DE ESTUDIO

OBJETIVO:

ASIGNATURA: AUTÓMATAS Y LENGUAJES FORMALES UNIDAD: 2. Autómatas finitos.

TEMA

Estudiar las máquinas abstractas más simples de reconocimiento de tokens en su concepción determinista y no determinista

HORAS

2.1. Definición y propiedades.

1

2.2. Estructura general.

1

2.3. Diagramas de transiciones.

2

2.4. Autómatas finitos deterministas (AFD).

3

2.5. Autómatas finitos no deterministas (AFN).

3

2.6. Autómatas finitos con transiciones épsilon.

1

2.7. Eliminación de las transiciones épsilon.

2

2.8. Equivalencias entre AFN y AFD.

3

2.9. Minimización de un AFD.

2

ACTIVIDADES DE APRENDIZAJE Investigación sobre las aplicaciones de los AFD y AFN

TÉCNICAS

APOYOS DIDÁCTICOS

Exposición y debate de temas en salón de clase.

Proyector, Computadora personal, diapositivas

Resolver ejercicios y problemas con AFD y AFN

Desarrollo de ejemplos y ejercicios

pizarrón Internet, libros

Resolver ejercicios y problemas para encontrar el Simulación de AFD y AFN AFD equivalente a un AFN Simular AFD y AFN utilizando herramientas en línea

Resolver de ejemplos y ejercicios de minimización de un AFD Utilizar un lenguaje de programación de alto nivel para programar la minimización de un AFD

HOJA 4 DE 11

UNIVERSIDAD DEL ISTMO PROGRAMA DE ESTUDIO

ASIGNATURA: AUTÓMATAS Y LENGUAJES FORMALES UNIDAD: 3. Expresiones y lenguajes regulares.

TEMA

OBJETIVO: Emplear las expresiones regulares para reconocer o describir los lenguajes aceptados o generados por estas

HORAS

3.1. Expresiones regulares.

2

3.2. Autómatas finitos y expresiones regulares.

4

3.3. Aplicaciones de las expresiones regulares.

4

3.4. Álgebra para las expresiones regulares.

4

3.5. Lema del bombeo.

2

3.6. Propiedades de la clausura.

2

ACTIVIDADES DE APRENDIZAJE Investigación sobre las aplicaciones de las expresiones y lenguajes regulares Resolver ejercicios y problemas de equivalencia entre AFD y expresiones regulares

TÉCNICAS

APOYOS DIDÁCTICOS

Exposición y debate de temas en salón de clase.

Proyector, Computadora personal, diapositivas pizarrón

Desarrollo de ejemplos y ejercicios

Internet, libros

Uso de simuladores en línea

Resolver ejercicios y problemas de aplicación de las expresiones regulares Usar un simulador para verificar el conjunto de cadenas aceptadas por un lenguaje regular

HOJA 5 DE 11

UNIVERSIDAD DEL ISTMO PROGRAMA DE ESTUDIO

ASIGNATURA: AUTÓMATAS Y LENGUAJES FORMALES

OBJETIVO: Utilizar las convenciones de notación apropiadas para reconocer o describir lenguajes con reglas inherentemente recursivas

UNIDAD: 4. Gramáticas independientes del contexto.

TEMA

HORAS

4.1. Definición y notación.

1

4.2. Jerarquía de Chomsky.

1

4.3. Derivaciones izquierda y derecha.

3

4.4. Lenguaje de una gramática.

3

4.5. Árboles de derivación.

3

4.6. Aplicaciones de las gramáticas independientes del contexto.

2

4.7. Ambigüedad en las gramáticas y lenguajes.

3

4.8. Gramáticas regulares.

3

ACTIVIDADES DE APRENDIZAJE Investigación sobre las aplicaciones de las gramáticas independientes del contexto Resolver ejercicios y problemas de aceptación de lenguajes sencillos independientes del contexto

TÉCNICAS

APOYOS DIDÁCTICOS

Exposición y debate de temas en salón de clase.

Proyector, Computadora personal, diapositivas pizarrón

Desarrollo de ejemplos y ejercicios

Internet, libros

Uso de simuladores en línea

Resolver ejercicios y problemas de generación de lenguajes sencillos independientes del contexto Resolver ejercicios y problemas de detección y eliminación de ambigüedad Usar un simulador para representar las derivaciones de una gramática libre de contexto

HOJA 6 DE 11

UNIVERSIDAD DEL ISTMO PROGRAMA DE ESTUDIO

ASIGNATURA: AUTÓMATAS Y LENGUAJES FORMALES UNIDAD: 5. Autómatas de pila.

TEMA

OBJETIVO: Estudiar la relación y aplicación de los autómatas de pila respecto a las gramáticas independientes del contexto

HORAS

5.1. Definición.

1

5.2. Notación gráfica.

2

5.3. Lenguajes aceptados por un autómata de pila.

5

5.4. Equivalencia entre autómatas de pila y gramáticas libres de contexto.

4

5.5. Autómatas de pila deterministas (APD).

4

ACTIVIDADES DE APRENDIZAJE Resolver ejercicios y problemas de lenguajes aceptados por un autómata de pila Resolver ejercicios y problemas de equivalencia entre autómatas de pila y GLC

TÉCNICAS

APOYOS DIDÁCTICOS

Exposición de temas en salón de clase.

Proyector, Computadora personal, diapositivas pizarrón

Desarrollo de ejemplos y ejercicios

Internet, libros

Uso de simuladores en línea

Resolver ejercicios y problemas de APD Usar un simulador para representar el funcionamiento de un autómata de pila

HOJA 7 DE 11

UNIVERSIDAD DEL ISTMO PROGRAMA DE ESTUDIO

ASIGNATURA: AUTÓMATAS Y LENGUAJES FORMALES UNIDAD: 6. Propiedades de los lenguajes independientes del contexto.

TEMA

HORAS

6.1. Formas normales para gramáticas independientes del contexto (GIC).

2

6.2. Lema del bombeo para lenguajes independientes del contexto (LIC).

4

6.3. Propiedades de la clausura de los LIC.

3

6.4. Propiedades de decisión de los LIC.

3

OBJETIVO: Identificar los lenguajes libres de contexto mediante el estudio de sus propiedades

ACTIVIDADES DE TÉCNICAS APRENDIZAJE Resolver ejercicios y Exposición de temas problemas utilizando el lema en salón de clase. del bombeo

APOYOS DIDÁCTICOS Proyector, Computadora personal, diapositivas pizarrón

Resolver ejercicios y problemas referentes a la clausura de los LIC

Desarrollo de ejemplos y ejercicios

libros

Resolver ejercicios y problemas de decisión de los LIC

HOJA 8 DE 11

UNIVERSIDAD DEL ISTMO PROGRAMA DE ESTUDIO

ASIGNATURA: AUTÓMATAS Y LENGUAJES FORMALES UNIDAD: 7. Máquina de turing.

TEMA

OBJETIVO: Identificar la importancia y aplicaciones de la máquina de turing

HORAS

7.1. Definiciones básicas.

1

7.2. Máquinas de Turing como aceptadores de lenguajes.

1

7.3. Construcción de máquinas de Turing.

2

7.4. Hipótesis de Turing – Church.

1

7.5. Máquina de turing universal.

3

7.6. Introducción a lenguajes decidibles.

1

7.7. El problema de paro.

2

ACTIVIDADES DE TÉCNICAS APRENDIZAJE Resolución de ejercicios y Exposición de temas problemas con máquinas de en salón de clase. turing como parsers

APOYOS DIDÁCTICOS Proyector, Computadora personal, diapositivas pizarrón

Resolución de ejercicios y Desarrollo de problemas con máquinas de ejemplos y ejercicios turing como calculadoras Resolución de problemas y ejercicios de decibilidad

Internet, libros

Uso de simuladores en línea

Usar un simulador para visualizar el funcionamiento de una máquina de turing

HOJA 9 DE 11

UNIVERSIDAD DEL ISTMO PROGRAMA DE ESTUDIO 7.- APOYO BIBLIOGRÁFICO TEXTO BÁSICO: • Lenguajes, gramáticas y autómatas, Rafael Cases, Luís Márquez, Alfaomega Editorial. 2002 • Introducción a la Teoría de Autómatas, Lenguajes y Computación, Hopcroft, Motwan, Ullman, Segunda Edición, Addison Wesley Editorial, 2002. • Teoría de Autómatas y Lenguajes Formales, García, Pérez, Ruiz, Segarra, Sempere, Vászquez de Parga, Alfaomega Editorial, 2001. • Introduction to the theory of computation, Michael Sipser, Second Edition, Course Technology Editor, 2005. TEXTO DE CONSULTA: • Automata theory with modern applications, James Anderson, Cambridge University Press, 2006. • Introducing the Theory of Computation, Wayne Goddard, First Edition, Jones & Bartlett Publishers, 2008. • An Introduction to Formal Language and Automata, Peter Linz, Fourth Edition, Jones & Bartlett Publisher, 2006.

8.- EVALUACIÓN

• Al inicio del curso el profesor indicará el procedimiento de evaluación, el cual deberá comprender las evaluaciones parciales y la ordinaria. El promedio de las calificaciones parciales representará el 50 % de la calificación final y el examen ordinario, el otro 50 %. • Las evaluaciones deberán ser por escrito y en su caso con apoyos orales y prácticos. • Para tener derecho a cada evaluación, el alumno deberá cumplir con un mínimo de 85 % de asistencia. • A criterio del profesor serán considerados los trabajos de investigación, tareas, exposiciones, proyectos y participación en clases. • Las evaluaciones parciales y la final, se efectuarán de acuerdo al calendario vigente, en los días y horas publicados por el Departamento de Servicios Escolares.

HOJA 10 DE 11

UNIVERSIDAD DEL ISTMO PROGRAMA DE ESTUDIO

M. en C. J. Jesús Arellano Pimentel

M. en C. Daniel Pacheco Bautista

ELABORÓ

FECHA DE ELABORACIÓN: FECHA DE APROBACIÓN:

Vo.Bo.

M en C. Víctor Manuel Martínez Rodríguez

APROBÓ

14 de enero de 2010

HOJA 11 DE 11