Guia docente 2024_25 Escuela Superior de Ingeniería Informática

Contenidos

Tema	Subtema
Introducción	Peliminares: conjuntos y funciones. Lenguages formales: Alfabetos, gramáticas Gramáticas formales: Jerarquía de Chomsky, derivaciones, árboles de derivación.
Lenguajes Regulares y Autómatas Finitos	Gramáticas Regulares y Expresiones Regulares. Autómatas Finitos. Propiedades de los Lenguajes Regulares. Gramáticas Regulares
Lenguajes Independientes del Contexto y Autómatas de Pila	Gramáticas Independientes del Contexto. Ambigüedad y Árboles de Derivación. Simplificación de Gramáticas Independientes del Contexto y Formas Normales. Autómatas de Pila. Propiedades de los Lenguajes Independientes del Contexto. Análisis sintáctico.
Lenguajes Recursivos Enumerables y Máquinas de Turing	Máquinas de Turing. Gramáticas sin restricciones. Decidibilidad y complejidad computacional.