Conceptos previos : Conceptos fundamentales de la teoría de conjuntos. Conceptos fundamentales de la teoría de autómatas. Ejercicios -- Autómatas finitos : Autómatas finitos. Elementos de un autómata finito. Definición formal de autómata finito determinista. Representaciones de los autómatas finitos deterministas. Representaciones de los autómatas finitos deterministas. El lenguaje de un autómata finito determinista. Ejemplos de lenguajes regulares. Autómatas finitos no deterministas. Equivalencia entre autómatas finitos deterministas y no deterministas. Ejercicios -- Gramáticas regulares : Definición de gramáticas regulares. Ejemplos de gramáticas regulares. Gramáticas regulares y autómatas finitos. Ejercicios -- Expresiones regulares : Introducción. Definición de las expresiones regulares. Lenguaje representado por un expresión regular. Autómatas finitos y expresiones regulares. Propiedades de las operaciones de las expresiones regulares. Ejercicios -- Propiedades de los lenguajes regulares y lenguajes no regulares : Propiedades de los lenguajes regulares. Introducción a los lenguajes no regulares. Introducción a la jerarquía de Chomsky. Ejercicios -- Lenguajes y gramáticas independientes del contexto : Definición de las gramáticas independientes del contexto. Derivaciones en las gramáticas independientes del contexto. Lenguaje de una gramática independiente del contexto. Introducción a los arboles de derivación. Forma normal de Chomsky. Transformación a forma normal de Chomsky. Ejercicios -- Autómatas a pila : Introducción a los autómatas a pila. Definición formal de un autómata a pila. Lenguajes aceptados por los autómatas a pila. Autómatas a pila y gramáticas independientes del contexto. Autómatas a pila deterministas. Ejercicios -- Propiedades de los lenguajes independientes del contexto : El lema de bombeo para lenguajes independientes del contexto. Los lenguajes independientes del contexto en la jerarquía de Chomsky. Propiedades delos lenguajes independientes del contexto. Ejercicios -- Introducción a las maquinas de Turing : Limites de la computación. Definición de una maquina de Turing. Descripciones instantáneas. Diagramas de transiciones para las maquinas de Turing. El lenguaje de una maquina de Turing: lenguaje recursivamente enumerables. Extensiones de máquina de Turing básica. Lenguajes recursivamente enumerables en la jerarquía de Chomsky. Ejercicios -- Ejercicios de autoevaluación -- Solución a los ejercicios.