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.