Lenguajes Formales, Autómatas y Computabilidad

Esta página es sobre la materia del plan de estudios 2023. Para ver la materia del plan 1993, consultar Teoría de Lenguajes.

Lenguajes Formales, Autómatas y Computabilidad

Año	Segundo año
Carga horaria	5 horas semanales
Correlativas	Algoritmos y Estructuras de Datos
Correlativa de	Complejidad Computacional

Lenguajes Formales, Autómatas y Computabilidad (LFAC) es una materia obligatoria de la Licenciatura en Ciencias de la Computación. Su objetivo es presentar los lenguajes formales y los autómatas que los reconocen, identificar los problemas que cada clase de autómatas puede resolver, así como sus limitaciones computacionales.

Información general sobre la cursada

La aprobación de los prácticos de LFAC consiste en dos parciales; no se realizan trabajos prácticos. La materia no es promocionable.

Desde el primer cuatrimestre de 2025, los parciales son formato multiple choice, aprobados (por separado) con nota 6 o superior. Se permite llevar una hoja A4 escrita a mano con los apuntes que se quiera.

Programa

• Definición de lenguaje formal y la jerarquía de Chomsky.
• Lenguajes regulares: autómatas finitos determinísticos y no determinísticos, expresiones regulares.
• Lenguajes no regulares y lema de bombeo para lenguajes regulares.
• Lenguajes libres de contexto: autómatas de pila, lenguajes determinísticos.
• Lenguajes no libres de contexto y lema de bombeo para lenguajes libres de contexto.
• Máquinas de Turing (determinísticas) y funciones parcialmente computables.
• Tesis de Church.
• Lenguaje $S++$ y codificación de programas
• Intérprete universal.
• El problema de la detención (Halting problem).
• Indecibilidad. Diagonalización. Reducciones.
• Teoremas del Parámetro, de la Recursión y de Rice.
• Lenguajes computables y computablemente enumerables.

Guías Prácticas

Primer Cuatrimestre 2025

• Práctica 1: Lenguajes
• Práctica 2: Autómatas Finitos
• Práctica 3: Determinización
• Práctica 4: Lema de Pumping para Lenguajes Regulares
• Práctica 5: Expresiones Regulares
• Práctica 6: Autómatas de Pila y Pumping para Lenguajes Libres de Contexto
• Práctica 7: Funciones Parcialmente Computables
• Práctica 8: Funciones No Computables y Diagonalización

Segundo Cuatrimestre 2024

• Repositorio con Práctica 1 resuelta

Parciales

Primeros parciales

Año	Cuatrimestre	Fecha	Instancia	Links

Segundos parciales

Año	Cuatrimestre	Fecha	Instancia	Links

Finales

Año	Cuatrimestre	Fecha	Instancia	Links