Teoría  de  autómatas  y  lenguajes  formales

+Info
DEPARTAMENTO PROFESOR/ES
MATEMÁTICAS Y COMPUTACIÓN María del Pilar Benito Clavijo
TITULACIONES EN LAS QUE SE IMPARTE LA ASIGNATURA
Titulación Carácter Curso Semestre Créditos Guía Docente
Grado en Ingeniería Informática Optativa 4 Primer Semestre 6 pdf
Grado en Matemáticas Optativa 4 Primer Semestre 6 pdf
CONTEXTO


Los fundamentos teóricos de la informática descansan en los lenguajes formales y el concepto de autómata, herramientas imprescindibles para adentrarse en muchos campos de las Ciencias de la Computación. Lenguajes y autómatas y los algoritmos que los relacionan son necesarios para comprender el funcionamiento de compiladores y procesadores, la descripción de datos, la especificación de interfaces y las capacidades de los procesos de cálculo.
COMPETENCIAS
COMPETENCIAS GENERALES:
CG1-Estar capacitado para analizar, razonar y evaluar de modo crítico, lógico y, en caso necesario, formal, sobre problemas que se planteen en su entorno.
CG2-Estar capacitado para, utilizando el nivel adecuado de abstracción, establecer y evaluar modelos que representen situaciones reales.
CG7-Haber desarrollado aquellas habilidades de aprendizaje necesarias para continuar su formación.
CG12-Capacidad para concebir, desarrollar y mantener sistemas, servicios y aplicaciones informáticas empleando los métodos de la ingeniería del software como instrumento para el aseguramiento de su calidad.
CG15-Conocimiento de las materias básicas y tecnologías, que capaciten para el aprendizaje y desarrollo de nuevos métodos y tecnologías, así como las que les doten de una gran versatilidad para adaptarse a nuevas situaciones.
CG17-Conocimientos para la realización de mediciones, cálculos, valoraciones, tasaciones, peritaciones, estudios, informes, planificación de tareas y otros trabajos análogos de informática.

TEMARIO


PRELIMINARES: Conjuntos y relaciones. Clausura Alfabetos y lenguajes. Descripción de lenguajes. Operaciones. Expresiones regulares.

LENGUAJES REGULARES Y SUS MÁQUINAS: Autómatas finitos deterministas y no deterministas. Métodos de diseño. Equivalencia entre autómatas finitos y expresiones regulares. Algoritmos de conversión. Lema de bombeo. Minimización.

LENGUAJES LIBRES DE CONTEXTO Y SUS MÁQUINAS: Gramáticas y generación de lenguajes. Jerarquía de Chomsky. Lenguajes libres de contexto. Autómatas con pila. Equivalencia entre autómatas con pila y lenguajes libres de contexto. Algoritmos de conversión.

INTRODUCCIÓN A MÁQUINAS TURING: Definición y funcionamiento de Máquinas Turing. Computación y decidibilidad Turing. Diseño de máquinas. Tesis de Church. Problemas insolubles.