Unidad 1 Introducción a los lenguajes formales Alfabetos, cadenas y lenguajes formales: definiciones básicas. Operaciones con cadenas. Operaciones con lenguajes. Propiedades de lenguajes.
Unidad 2 Lenguajes regulares Autómata finito: definiciones básicas; ejemplos. Autómata finito determinístico: reconocimiento y traducción. Autómata finito no determinístico. Equivalencia entre autómata finito determinístico y no determinístico. Minimización de autómatas finitos. Aplicaciones de autómatas finitos. Gramáticas regulares. Algoritmo para obtener una gramática regular a partir de un autómata finito. Expresiones regulares: definiciones y aplicaciones prácticas. Leyes algebraicas de expresiones regulares. Relación entre lenguajes regulares, autómatas finitos, gramáticas regulares y expresiones regulares. Propiedades de clausura de los lenguajes regulares.
Unidad 3 Lenguajes libres del contexto Autómata de pila: definiciones básicas; ejemplos. Autómata de pila determinístico: reconocimiento y traducción. Autómata de pila no determinístico. Gramáticas libres del contexto. Árbol de derivación. Ambigüedad. Relación entre lenguajes libres del contexto, autómatas de pila y gramáticas libres del contexto. BNF (Backus Naur Form). BNF extendido y diagramas sintácticos. Propiedades de clausura de los lenguajes libres del contexto.
Unidad 4 Lenguajes sensibles al contexto y estructurados por frases Máquina de Turing: definiciones básicas; ejemplos. Máquina de Turing determinística: reconocimiento, traducción y cálculo de funciones. Máquina de Turing multicinta. Máquina de Turing no determinística. Autómata linealmente acotado. Gramáticas sensibles al contexto. Relación entre lenguajes sensibles al contexto, autómata linealmente acotado y gramáticas sensibles al contexto. Máquina de Turing y lenguajes estructurados por frases.
Unidad 5 Jerarquía de Chomsky Jerarquía de Chomsky: autómatas, gramáticas y lenguajes. Relación entre clases de lenguajes.
Unidad 6 Nociones básicas de computabilidad Relación entre problemas y lenguajes. Procedimiento y algoritmo. Lenguajes recursivos y recursivo enumerables, problemas de decisión: definiciones básicas y ejemplos. El problema del Halting.
|