Datos Identificativos | 2014/15 | |||||||||||||
Asignatura | Teoría de Autómatas e Linguaxes Formais | Código | 614311302 | |||||||||||
Titulación |
|
|||||||||||||
Descriptores | Ciclo | Período | Curso | Tipo | Créditos | |||||||||
1º e 2º Ciclo | 2º cuadrimestre |
Terceiro | Troncal | 8 | ||||||||||
|
Temas | Subtemas |
Preliminares matemáticos | Lógica elemental Teoría de conjuntos Relaciones y funciones Inducción matemática Cardinalidad |
Lenguajes formales | Alfabetos, palabras y lenguajes Operaciones con palabras Operaciones con lenguajes |
Lenguajes regulares y autómatas finitos | Lenguajes sobre alfabetos Lenguajes regulares y expresiones regulares Autómata finito determinista (AFD) Autómata finito no determinista (AFN) Equivalencia entre AFNs y AFDs Autómata finito con epsilon transiciones Autómatas finitos y expresiones regulares Aplicaciones prácticas de las expresiones regulares y de los autómatas finitos |
Lenguajes independientes del contexto y autómatas de pila | Gramáticas regulares Gramáticas regulares y lenguajes regulares Gramáticas independientes del contexto Arboles de derivación y ambigüedad Simplificación de gramáticas independientes del contexto Propiedades de los lenguajes independientes del contexto Algoritmos de análisis sintáctico Autómatas de pila Forma normal de Greibach |
Máquinas de Turing | Definiciones básicas Máquinas de Turing como aceptadoras de lenguajes Construcción de máquinas de Turing Modificaciones de las máquinas de Turing Máquina de Turing universal |
Lenguajes recursivamente enumerables | Lenguajes aceptados por máquinas de Turing Lenguajes regulares e independientes del contexto como lenguajes recursivos Propiedades de los lenguajes recursivos y recursivamente enumerables Gramáticas no restringidas y lenguajes recursivamente enumerables Lenguajes sensibles al contexto y la jerarquía de Chomsky |
Resolubilidad | El problema de la parada El problema de correspondencia de Post Problemas no decidibles en lenguajes independientes del contexto |
Computabilidad | Fundamentos de la teoría de funciones recursivas Alcance de las funciones recursivas primitivas Funciones recursivas parciales El poder de los lenguajes de programación |
Introducción a la teoría de la complejidad computacional | Complejidad algorítmica Modelo general de cómputo y complejidad computacional Tiempo y espacio en máquinas de Turing Las distintas clases de complejidad Los problemas tratables y no tratables Reducibilidad en tiempo polinómico Problemas NP-completos |