Lenguajes Formales, Autómatas y Computabilidad

Materia: Inteligencia Artificial
Departamento: Inteligencia Artificial
Créditos ECTS: 6
Semestre: 3
Carácter: Básica

Resultados de aprendizaje

• Modelar mediante procedimientos finitos conjuntos y lenguajes infinitos.
• Adquirir destreza en la aplicación de los diferentes métodos de demostración.
• Distinguir y reconocer las distintas clases de lenguajes y sus autómatas asociados según la jerarquía de Chomsky.
• Conocer modelos de cómputo universales así como los límites de lo que puede o no ser computado mediante un algoritmo.   

Breve descripción de los contenidos

1. Teoría y diseño de lenguajes formales y gramáticas
2. Teoría y diseño de autómatas finitos y autómatas con pila
3. Máquinas de Turing y modelos de cómputo universales
4. Teoría de la computabilidad

Bibliografía

1. Lenguajes, gramaticas y automatas. Un enfoque Práctico. P. Isasi., P. Martínez, D. Borrajo. Addison-Wesley, 1997.
2. Introduction to automata theory, languages and computation. J.E. Hopcroft, J.D. Ullman. Editorial Addison-Wesley 1979.
3. Introduction to the theory of computation. Michael Sipser. Ed. Thomson 2006.