Livres sur la théorie des automates pour l'auto-apprentissage

J'ai besoin d'un livre de théorie des automates finis avec beaucoup d'exemples que je peux utiliser pour l'auto-apprentissage et pour préparer les examens.

La référence classique est « Introduction à la théorie, aux langages et au calcul des automates » (par Hopcroft, Motwani et Ullman). Certaines personnes recommandent également les " langages formels et leur relation avec les automates " beaucoup plus anciens (par Hopcroft et Ullman).

Moi, cependant, j'aime " Introduction à la théorie du calcul " (par Sipser). Il est très bien écrit et est un livre relativement nouveau.

J'ai un faible pour les automates et la calculabilité de Dexter Kozen ( table des matières et exemples de chapitres [PS]). Il est assez complet et couvre des sujets avancés très intéressants. Les preuves sont formelles et explicites et la notation et le formatage sont charmants. Plus important encore, les exercices sont excellents, donc selon le niveau de vos examens, ce sera un bon matériel d'étude.

Celui que j'utilise le plus pour mes cours est Elements of Automata Theory de Jacques Sakarovitch, Cambridge University Press, 2009. Son champ d'application peut être un peu différent des autres, car il couvre également largement les aspects algébriques, les séries de pouvoirs formelles, et transductions. Et il y a de nombreux exercices.

"Combinatoire appliquée aux mots", par Lothaire, 2004

Est de loin mon préféré. Des tonnes d'exemples, et se développe également à partir des bases absolues jusqu'à des applications d'automates assez intéressantes comme la reconnaissance automatique de la parole avec des transducteurs à état fini pondérés et des sujets en bioinformatique.

Mieux encore, il est gratuit à télécharger et comprend également des ensembles de solutions:

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

"Résolution de problèmes dans les automates, les langues et la complexité" de Du-Ko est l'un de mes préférés après Sipser, HU et Kozen. Il contient de nombreuses solutions aux * rd problèmes de Kozen et sipser avec de nombreux exemples et exercices associés. Particulièrement utile pour la préparation aux examens.

Je ne suis pas sûr que ce soit le meilleur livre pour se préparer aux examens, mais le livre

Automates finis; Comportement et synthèse par BA Trakhtenbrot et Ya. M. Barzdinʹ

est assez bon. Il a un nombre surprenant d'excellents résultats que j'ai trouvé particulièrement utiles dans la recherche.

Introduction aux langages et à la théorie du calcul

John C. Martin

Je recommande fortement ce livre pour un débutant et c'est un choix parfait pour quelqu'un qui cherche de nombreux exemples.

J'apprécie les notes de cours suivantes de Jarkko Kari: http://users.utu.fi/jkari/automata/

Bref aperçu du cours:

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

Il existe également des éléments de la théorie du calcul de H.Lewis et C.Papadimitriou. C'est une introduction bien écrite à la théorie des automates.

Comprendre le calcul

Des machines simples aux programmes impossibles

Il couvre beaucoup de choses, y compris la théorie des automates. Les exemples sont présentés en Ruby et ils sont assez faciles à comprendre. Vous aurez peut-être besoin d'un autre livre si vous souhaitez approfondir la théorie, mais celui-ci est idéal pour apprendre les bases.

"Formal Languages ​​And Automata Theory" par AA Puntambekar est le meilleur livre pour des exemples résolus. La plupart du livre ne contient que des exemples résolus et peu de théorie. C'est bon de passer les examens.