Mat 08289 201810 1

Materia: Informática Teórica
Código: 08289
Prerrequisito: Matemática Discreta (08276)
Programas: Ingeniería de sistemas
Período académico: 18-1 (Primer semestre de 2018)
Intensidad semanal: 4 horas
Créditos 3
I. OBJETIVO GENERAL
Al finalizar exitosamente este curso el estudiante será competente en el empleo de los conceptos y técnicas propias
de los lenguajes formales y de los autómatas que los reconocen, y de algunas de sus aplicaciones fundamentales.
II. OBJETIVOS TERMINALES
Como resultado de participar en este curso y de cumplir con sus compromisos en el proceso de aprendizaje activo,
el estudiante estará en capacidad de:
a) Probar que una relación dada es relación de equivalencia, y determinar sus clases de equivalencia y el conjunto
cociente correspondientes.
b) Calcular el autómata reducido y conexo equivalente a uno dado.
c) Establecer si dos autómatas dados son o no equivalentes, como aplicación del algoritmo del punto anterior.
d) Enunciar y explicar los conceptos fundamentales de gramáticas formales y su relación con los lenguajes que
ellas generan.
e) Relacionar los lenguajes formales con autómatas abstractos, y utilizar la estructura de los autómatas para
estudiar la estructura de los lenguajes.
f) Caracterizar los autómatas de estados finitos, los autómatas de pila y las máquinas de Turing como modelos
de computación con caracterıś ticas propias, que determinan su aplicabilidad como herramientas para el
modelado de problemas en informática.
g) Describir los lım
́ ites computacionales de las máquinas abstractas y de los computadores.
h) Programar alguno o algunos de los algoritmos estudiados en desarrollo del curso.
III. OBJETIVOS ESPECIFICOS
UNIDAD 0: Revisión métodos de demostración y relaciones de equivalencia. Conjuntos numerables y conjuntos

no numerables. (2 semanas)
UNIDAD 1: Autómatas de Mealy y de Moore. Autómatas reducidos y conexos. (1 semana)

1. Calcular el autómata mın
́ imo (reducido y conexo) equivalente a uno dado.
2. Establecer la equivalencia o no entre dos autómatas dados.
UNIDAD 2. Lenguajes regulares y autómatas finitos. (4 semanas)

1. Definir formalmente y dar ejemplos de alfabeto, cadena, concatenación de cadenas,
lenguaje sobre un alfabeto y operaciones sobre lenguajes.
2. Definir formalmente autómata finito, dar ejemplos e identificar los elementos en un autómata.
3. Establecer la identidad conceptual entre expresión regular y lenguaje regular y describir el lenguaje
representado por una expresión regular o hallar la expresión regular que representa un lenguaje dado.
4. Describir la equivalencia entre expresiones regulares y autómatas finitos.
5. Transformar un AFN o un AFN- en un AFD equivalente.
6. Calcular el lenguaje reconocido por un AF. Construir el AF para un lenguaje dado.
7. Enunciar el lema del bombeo para lenguajes regulares y aplicarlo para establecer la no regularidad de un
lenguaje dado.
8. Aplicar las propiedades de clausura de lenguajes regulares en la determinación de la regularidad o no de
otros lenguajes, a partir de ellas.
UNIDAD 3. Gramáticas y lenguajes independientes del contexto. Autómatas de pila. (4 semanas)

1. Definir gramática independiente del contexto y construir GIC para lenguajes dados.
2. Explicar el concepto de ambigüedad lingüıś tica y aplicarlo a GIC ambiguas.
3. Definir gramática regular y establecer la relación entre GRD y AF.
4. Construir la GIC en forma normal de Chomsky, equivalente a una GIC dada.
5. Enunciar y aplicar el lema de bombeo para LIC.
6. Aplicar las propiedades de clausura de LIC para decidir si un lenguaje dado es o no LIC.
7. Definir autómata de pila como modelo computacional y describir sus componentes.
8. Determinar el lenguaje aceptado por un AFP, tanto determinista como no determinista.
9. Dado un LIC, establecer el AFPN que lo reconoce.
UNIDAD 4. Máquinas de Turing (4 semanas)

1. Definir formalmente la máquina de Turing y precisar sus componentes.
2. Construir máquinas de Turing como reconocedoras de lenguajes, como generadoras de lenguajes y como
calculadoras de funciones.
3. Describir y utilizar las variantes más comunes de las máquinas de Turing.
4. La definición de algoritmo. El programa de Hilbert del 1900.
5. Enunciar y explicar la tesis de Church-Turing y sus alcances.
6. Codificar máquinas de Turing y cadenas sobre un alfabeto dado.
UNIDAD 5 Decidibilidad (1 semana)

1. Concepualizar la Máquina universal de Turing y el lenguaje universal.
2. Demostrar que el lenguaje diagonal no es recursivamente enumerable.
3. Establecer la existencia de lenguajes no recursivos: el lenguaje universal.
4. Establecer la indecidibilidad de algunos problemas clásicos en teorıa
́ de la computación.
IV. METODOLOGÍA
1. El enfoque: En concordancia con la misión de la Universidad, el aprendizaje de los temas de este curso será el
resultado del proceso de construcción del conocimiento, adelantado por el estudiante y guiado por el profesor.
Parte fundamental de este proceso es el aprovechamiento del estudio previo hecho por los estudiantes, como
elemento generador de preguntas, discusiones y conclusiones.
2. La discusión en clase: La discusión, orientada por el profesor es el elemento central en la metodología del
curso. Se fundamenta en el estudio preliminar de las secciones asignadas, en las preguntas de los estudiantes
y en sus respuestas a sus preguntas y a las del profesor, que alimenten el proceso de aprendizaje activo. El
profesor interviene esencialmente como guía y moderador de las discusiones, y se encarga de hacer la síntesis
final para socializar el conocimiento consolidado en clase y de indicar al estudiante la labor que debe realizar
como preparación para la clase siguiente y los objetivos que debe alcanzar como parte de tal preparación.
3. Las actividades del estudiante: Para el logro de los objetivos de aprendizaje el estudiante debe desarrollar con
total responsabilidad un conjunto de actividades antes, durante y después de la clase, así:
Antes de la clase
 Realizar todas las actividades indicadas por el profesor para la preparación del tema de clase, hacer
explícitas las dudas e inquietudes que le surjan como resultado de este proceso y preparar las preguntas
que formulará durante la clase de presentación del tema, con el fin de resolver las dudas e inquietudes.
Durante la clase
 Participar activamente en las discusiones que se generen a partir de las preguntas formuladas por los
estudiantes y por el profesor, y de las respuestas a las mismas. Igualmente, presentar las dudas e
inquietudes que le surgieron al prepararse para esta clase, y discutir alternativas propias de solución de
problemas, cuando las tenga.
Después de la clase
 Asegurarse de consolidar el nuevo conocimiento resolviendo ejercicios y problemas que en la fase de

preparación no haya podido resolver, o que revisten mayor complejidad, y relacionándolo con
conocimientos previamente adquiridos.
V. EVALUACIÓN
 Control de estudio previo 10%

 Tres pruebas cortas 20%
 Tareas 10%
 Dos exámenes parciales 35%
 Examen Final 25%
Nota importante: De conformidad con la política oficial del Departamento de Matemáticas y Estadística
para las materias que tienen examen final acumulativo, si la calificación así calculada está entre 2.8 y 3.0
pero la nota del examen final es mayor o igual a 3.3, la nota final será 3.0.
VI. TEXTO GUÍA
Teorı́a de la computación: lenguajes, autómatas, gramáticas. Rodrigo de Castro. Colección Notas de Clase,
Facultad de Ciencias, Universidad Nacional de Colombia, 2003
VII. BIBLIOGRAFÍA
1. Teorı́a de la computación. Carrión Viramontes. Editorial Limusa, 2009.

2. Lenguajes formales y teorı́a de la computación. John Martin. Mc Graw-Hill. 3ra. edición, 2004
3. Introduction to the Theory of computation (Second Edition. International Edition). Michael Sipser.
Thompson course technology, 2006.
4. Introducción a la teorı́a de autómatas, lenguajes y computación. Hopcroft, Montovani, Ullman. Addison
Wesley. 2002
5. Machines, Languages and Computation. Denning, Dennis, Qualitz. Prentice-Hall, 1978.

Mat 08289 201810 1

Cargado por

Copyright:

Formatos disponibles

Mat 08289 201810 1

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Mat 08289 201810 1

Cargado por

Copyright:

Formatos disponibles

Materia: Informática Teórica

II. OBJETIVOS TERMINALES

III. OBJETIVOS ESPECIFICOS

UNIDAD 0: Revisión métodos de demostración y relaciones de equivalencia. Conjuntos numerables y conjuntos

UNIDAD 1: Autómatas de Mealy y de Moore. Autómatas reducidos y conexos. (1 semana)

UNIDAD 2. Lenguajes regulares y autómatas finitos. (4 semanas)

UNIDAD 3. Gramáticas y lenguajes independientes del contexto. Autómatas de pila. (4 semanas)

UNIDAD 4. Máquinas de Turing (4 semanas)

UNIDAD 5 Decidibilidad (1 semana)

 Asegurarse de consolidar el nuevo conocimiento resolviendo ejercicios y problemas que en la fase de

 Control de estudio previo 10%

VI. TEXTO GUÍA

1. Teorı́a de la computación. Carrión Viramontes. Editorial Limusa, 2009.

También podría gustarte