Livros sobre teoria dos autômatos para auto-estudo

Preciso de um livro de teoria de autômatos finito com muitos exemplos que eu possa usar para auto-estudo e preparação para exames.

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.

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.

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.

"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/

"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.

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.

Introdução às linguagens e teoria da computação

John C. Martin

Eu recomendo este livro para iniciantes e essa é a escolha perfeita para quem procura muitos exemplos.

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

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

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.

"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.