Profesor: Luis Amable García Fernández

Información general: 

Esta asignatura, de gran contenido teórico, se ubica en segundo curso y tiene carácter troncal. Sus contenidos están orientados a exponer los principios científicos que han dado soporte a la noción matemática de computación: la definición, análisis y diseño de máquinas abstractas. Estas máquinas abstractas son capaces de reconocer lenguajes (que  no son más que un conjunto de cadenas que cumplen cierta propiedad). El estudio de estos lenguajes permite clasificarlos en cuatro categorías que, junto con sus máquinas asociadas, permiten establecer un gran número de cuestiones teóricas referentes a los recursos necesarios por un modelo de autómata para resolver un determinado problema. Cuestiones fundamentales que afectan a la informática, como por ejemplo, ¿Cómo se define un lenguaje de programación?, ¿Cuál es el modelo de computación más potente que existe?, ¿Puede superarse?, ¿Existe algún límite al tipo de problemas que puede resolver un computador?, ¿Cómo se puede medir la cantidad de recursos que se necesitan como máximo para resolver un problema?, ... serán tratadas en esta asignatura.

Con el propósito de acercar estos resultados teóricos a las aplicaciones prácticas el alumno realizará, mediante las herramientas software adecuadas, una implementación de un traductor de un lenguaje de programación a otro. De esta forma se establece la relación entre las máquinas abstractas expuestas en teoría y, cómo pueden ser utilizadas en la práctica para resolver problemas.

Conocimiento previos recomendables:

Sin ser requesitos oficiales, son muy convenientes para poder superar esta asignatura, tener una buena formación en matemáticas (por ejemplo, haber superado las asignaturas de matemáticas de primer curso, fundamentalmente la asignatura IS05) y de programación (haber superado la asignatura IS04).
 
Objetivos:
Conocer qué es un lenguaje formal y cuál es su equivalencia con un problema, 

Conocer qué es el no determinismo y las consecuencia que 
aporta su introducción en cada uno de los modelos formales 
estudiados en la asignatura, 

Ser capaz de identificar cuál es el modelo más restrictivo de máquina 
abstracta necesario para reconocer un determinado 
lenguaje, 

Conocer los distintos modelos de Autómatas Finitos y sus 
equivalencias, y ser capaz de diseñar Autómatas Finitos y establecer 
correctamente las equivalencias entre ellos, 

Conocer las Expresiones Regulares y las Gramáticas Regulares y ser capaz de 
manipularlas correctamente, 

Conocer las Gramáticas de Contexto Libre y su Formas 
Normales y ser capaz de escribir Gramáticas de Contexto Libre 

Conocer los tipos de Autómatas de Pila y sus relaciones con 
Gramáticas de Contexto Libre, y ser capaz de diseñar 
Autómatas de Pila, 

Conocer qué es una Máquina de Turing, sus modificaciones 
y ser capaz de diseñar Máquinas de Turing simples, tanto para 
reconocer como para generar lenguajes, 

Conocer la Tesis de Church-Turing y las implicaciones del 
Teorema de Gödel, y conocer el modelo de Máquina Universal 
de Turing y las implicaciones de la indecidibilidad, 

Conocer las clases de complejidad espacial y temporal y 
los resultados que las relacionan, especialmente los relacionados 
con las clases P y NP, 

Conocer, y ser capaz de aplicar correctamente, las propiedades 
de clausura de los distintos tipos de lenguajes. 
 
Temario:

Conceptos básicos

Repaso de la nomenclatura y operaciones algebráicas que se emplean en la asignatura. 

Introducir el concepto de lenguaje y el de gramática. 

Describir la clasificación de tipos de gramáticas seg'ñun Noam Chomsky. 

Describir los tipos de máquinas abstractas básicas en la asignatura.

Lenguajes Regulares: Autómatas Finitos y Expresiones Regulares.

2.1 Autómatas Finitos Deterministas (AFD).

2.2 Autómatas Finitos No Deterministas (AFN).

2.3 Autómatas Finitos con Movimientos Libres (AFlambda).

2.4 Expresiones Regulares.

2.5 Otros tipos de Autómatas Finitos.

2.6 Aplicaciones.

Propiedades de los Lenguajes Regulares.

3.1 Teorema de Myhill-Nerode. Minimización de Autómatas Finitos.

3.2 Lema de Bombeo.

3.3 Propiedades de Clausura.

3.4 Algoritmos de Decisión para Lenguajes Regulares.

Lenguajes de Contexto Libre: Gramáticas de Contexto Libre y Autómatas de Pila.

4.1 Gramáticas y Lenguajes de Contexto Libre.

4.2 Árboles de Derivación.

4.3 Simplificación de GCL.

4.4. Autómatas de Pila No Deterministas y Deterministas.

Propiedadades de los Lenguajes de Contexto Libre.

5.1 Lema de Bombeo.

5.2 Propiedades de Clausura.

5.3 Algoritmos de Decisión.

La Máquina de Turing

Modelo estándar. Modifiicaciones del Modelo de Máquina de Turing. La Máquina de Turing como generador

Computabilidad

Lenguajes Recursivos y Lenguajes Recursivamente Enumerables. Propiedades de estos lenguajes.

Decidibilidad

La Máquina Universal de Turing. Existencia de Lenguajes no Recursivamente Enumerables. El Problema de la Parada

Módulos/Bloques temáticos