Universidade do Minho  

       
 
  Autenticação/Login
 
Homepage
Contactos
Mapa do Site
   
  imprimir
 
voltar 
OITO
autómatos e máquinas de turing
josé carlos costa
 
 
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 
 
voltar 
 
  © 2024 Universidade do Minho  - Termos Legais  - actualizado por DMAT Símbolo de Acessibilidade na Web D.