Teoría de Autómatas y Lenguajes formales
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:
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.
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 generadorComputabilidad
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 ParadaMódulos/Bloques temáticos
-
Temario de la asignatura [4]
IS17