1. Introducción.

1. Alfabetos, palabras y lenguajes.
2. Procedimientos para definir lenguajes: Expresiones regulares y Gramáticas.
3. Procedimientos para reconocer lenguajes: Autómatas y Máquinas de Turing.
4. Aplicaciones.

2. Lenguajes Regulares.

1. Autómatas finitos.

1. Autómatas finitos deterministas (AFD).
2. Minimización de autómatas finitos deterministas.
3. Autómatas finitos indeterministas (AFI).
4. Equivalencia entre AFD y AFI.

2. Expresiones regulares.

1. Operaciones y funciones sobre palabras.
2. Operaciones sobre lenguajes.
3. Definición de Expresión Regular.
4. Operaciones sobre lenguajes regulares. Propiedades.

3. Lema de bombeo para lenguajes regulares.

3. Lenguajes Independientes del Contexto.

1. Propiedad de No Regularidad.
2. Autómatas a Pila.

1. Autómatas a pila deterministas e indeterministas.

3. Gramáticas. Gramáticas Independientes del Contexto.

1. Ambigüedad.
2. Formas Normales de Chomsky y de Greibach.

4. Operaciones sobre lenguajes independientes del contexto. Propiedades.
5. Lema de bombeo para lenguajes independientes del contexto.

4. Lenguajes recursivos y recursivamente enumerables.

1. Propiedad de No Independencia del Contexto.
2. Máquinas de Turing.

1. Submáquinas de Turing.
2. Máquinas de Turing deterministas e indeterministas.
3. Equivalencias.

3. Gramáticas dependientes del contexto.
4. Definición de Lenguaje Recursivamente Enumerable.
5. Definición de Lenguaje Recursivo.
6. Computabilidad y Decidibilidad.
7. Máquina de Turing Universal.
8. Propiedades de los lenguajes recursivamente enumerables.
9. Problema de la parada.