Temas Subtemas
Preliminares sobre linguaxes formais Alfabetos, palabras e linguaxes
Linguaxes regulares e expresións regulares
Autómatas finitos
Linguaxes independentes do contexto e autómatas de pila Gramáticas regulares
Gramáticas regulares e linguaxes regulares
Gramáticas independentes do contexto
Árbores de derivación e ambigüidade
Simplificación de gramáticas independentes do contexto
Propiedades das linguaxes independentes do contexto
Algoritmos de análise sintáctico
Autómatas de pila
Forma normal de Greibach
Máquinas de Turing Definicións básicas
Máquinas de Turing como aceptadoras de linguaxes
Construción de máquinas de Turing
Modificacións das máquinas de Turing
Máquina de Turing universal
Linguaxes recursivamente enumerables Linguaxes aceptadas por máquinas de Turing
Linguaxes regulares e independentes do contexto como linguaxes recursivas
Propiedades das linguaxes recursivas e recursivamente enumerables
Gramáticas non restrinxidas e linguaxes recursivamente enumerables
Linguaxes sensibles ao contexto e a xerarquía de Chomsky
Resolubilidade O problema da parada
O problema de correspondencia de Post
Problemas non decidibles en linguaxes independentes do contexto
Computabilidade Fundamentos da teoría de funcións recursivas
Alcance das funcións recursivas primitivas
Funcións recursivas parciais
O poder das linguaxes de programación