publicação do departamento de matemática
da universidade do minho
março, 2004
ISBN: 972-8810-07-5
Este texto foi escrito para servir de apoio às aulas da disciplina de Autómatos e Máquinas de Turing, da Licenciatura em Matemática e Ciências de Computação da Universidade do Minho, no ano lectivo 2003/2004.
Nele são apresentados os fundamentos da teoria de linguagens formais e autómatos finitos e é feita uma breve introdução às máquinas de Turing. Em cada capítulo são propostos exercícios relativos aos conteúdos aí expostos.
conteúdo
1 Preliminares
1.1 Funções e relações
1.2 Conjuntos numeráveis e conjuntos não numeráveis
1.3 Indução
1.4 Conjuntos definidos indutivamente
1.5 Funções definidas indutivamente
1.6 Grafos orientados
1.7 Exercícios
2 Linguagens
2.1 Palavras e linguagens
2.2 Operações sobre linguagens
2.3 Expressões e linguagens regulares
2.4 Equações lineares
2.5 Exercícios
3 Autómatos Finitos
3.1 Noções Básicas
3.2 Linguagens reconhecíveis
3.3 Autómatos deterministas
3.4 Autómatos com transições vazias
3.5 Teorema de Kleene
3.5.1 Operações e autómatos
3.5.2 Representação de autómatos por sistemas de equações lineares
3.6 Minimização de autómatos
3.7 Exercícios
4 Máquinas de Turing
4.1 Noções básicas
4.2 Representação gráfica de máquinas de Turing
4.3 Composição sequencial de máquinas de Turing
4.4 Cálculo de funções com máquinas de Turing
4.5 Variante de máquinas de Turing
4.5.1 Máquinas de Turing com mais do que uma fita
4.5.2 Máquinas de Turing não ? deterministas
4.6 Linguagens recursivas e linguagens recursivamente enumeráveis
4.7 Exerícios
Bibliografia
|