Guia docenteCurso
Facultad de Informática
  Inicio | galego | castellano | english | A A |  
Grao en Enxeñaría Informática
 Asignaturas
  Teoría de la computación
   Contenidos
Tema Subtema
Preliminares sobre lenguajes formales Alfabetos, palabras y lenguajes
Lenguajes regulares y expresiones regulares
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
Universidade da Coruña - Rúa Maestranza 9, 15001 A Coruña - Tel. +34 981 16 70 00  Soporte Guías Docentes