Livros sobre teoria dos autômatos para auto-estudo

Respostas:

35

A referência clássica é " Introdução à teoria de autômatos, linguagens e computação " (de Hopcroft, Motwani e Ullman). Algumas pessoas também recomendam as muito mais antigas " Línguas formais e sua relação com os autômatos " (de Hopcroft e Ullman).

Eu, no entanto, gosto de " Introdução à Teoria da Computação " (de Sipser). Está muito bem escrito e é um livro relativamente novo.

Sadeq Dousti
fonte
8
Eu segundo Sipster. Eu o uso no meu curso.
Dave Clarke
2
Passei o verão inteiro fazendo problemas com o antigo livro da HU. Tempos divertidos ...
Suresh Venkat
8
Eu prefiro Hopcroft & Ullman sem Motwani. HU&M eliminou todos os bons problemas!
Jeffε
3
@ user1652: Acho que você não encontrará algo com mais exemplos do que o livro de Linz. Você também pode dar uma olhada em "Introdução à teoria dos computadores", de Daniel Cohen. Tem muitos exemplos, mas é um livro mais antigo e talvez não seja tão legível quanto Linz.
Kurt
2
@Kurt: Seus comentários são bons demais para serem deixados como apenas comentários! Por que não publicá-las como respostas?
MS Dousti 07/10/10
9

Eu tenho uma queda por Automata e Computabilidade por Dexter Kozen ( sumário e capítulos de amostra [PS]). É bastante completo e aborda alguns tópicos avançados realmente interessantes. As provas são formais e explícitas e a notação e formatação são adoráveis. Mais importante ainda, os exercícios são excelentes, portanto, dependendo do nível de seus exames, será um bom material de estudo.

mikero
fonte
9

O que eu mais uso nos meus cursos é Elements of Automata Theory, de Jacques Sakarovitch, Cambridge University Press, 2009. Seu escopo pode ser um pouco diferente dos outros, pois também abrange extensamente aspectos algébricos, séries de poder formais, e transduções. E há muitos exercícios.

Sylvain
fonte
11
Se estamos falando apenas da teoria dos autômatos, este deve ser o melhor livro sobre o assunto. Estou lendo e adorando!
Marcos Villagra
5

"Combinatória Aplicada às Palavras", de Lothaire, 2004

É de longe o meu favorito. Cargas de exemplos e também se baseiam no básico absoluto, até alguns aplicativos de autômatos bastante interessantes, como o Reconhecimento Automático de Fala com Transdutores de Estado Finito Ponderado e tópicos em bioinformática.

O melhor de tudo é que é gratuito para download e também inclui conjuntos de soluções:

http://www-igm.univ-mlv.fr/~berstel/Lothaire/

s8soj3o289
fonte
5

"Solução de problemas em autômatos, idiomas e complexidade" de Du-Ko é um dos meus favoritos depois de Sipser, HU e Kozen. Ele contém muitas soluções para os primeiros problemas de Kozen e sipser, com inúmeros exemplos e exercícios relacionados. Especialmente útil para a preparação para o exame.

Shambo
fonte
5

Não tenho certeza se este é o melhor livro para se preparar para os exames, mas o livro

Autômatos finitos; Comportamento e síntese por BA Trakhtenbrot e Ya. M. Barzdinʹ

é muito bom Tem um número surpreendente de ótimos resultados que achei especialmente úteis em pesquisas.

Lev Reyzin
fonte
1

Gosto das seguintes notas de aula de Jarkko Kari: http://users.utu.fi/jkari/automata/

Breve resumo do curso:

Regular languages
    Finite automata, regular expressions
    Kleene theorem
    Pumping lemma
    Closure properties and decision algorithms
    State minimization, Myhill-Nerode theorem

Context-free languages
    Grammars, parsing
    Normal forms
    Pushdown automata
    Pumping lemma
    Closure properties and decision algorithms

Turing machines
    Recursive and recursively enumerable languages
    Universal Turing machines
    Undecidability of the halting problem (Turing)
    Reductions, other undecidable problems
subshift
fonte
1

Há também elementos da teoria da computação de H.Lewis e C.Papadimitriou. É uma introdução bem escrita à teoria dos autômatos.

Yannis Ntallas
fonte
0

Noções básicas sobre computação

De máquinas simples a programas impossíveis

Ele cobre muitas coisas, incluindo a teoria dos autômatos. Os exemplos são apresentados em Ruby e são muito fáceis de entender. Você pode precisar de outro livro se quiser aprofundar a teoria, mas este é ótimo para aprender o básico.

guhemama
fonte
0

"Línguas formais e teoria dos autômatos", de AA Puntambekar, é o melhor livro para exemplos resolvidos. A maior parte do livro contém apenas exemplos resolvidos e pouca teoria. É bom passar nos exames.

Prateek Bhuwania
fonte