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

Réponses:

35

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.

Sadeq Dousti
la source
8
J'appuie Sipster. Je l'utilise pour mon cours.
Dave Clarke
2
J'ai passé tout un été à faire des problèmes avec l'ancien livre HU. Des moments de plaisir ...
Suresh Venkat
8
Je préfère fortement Hopcroft & Ullman sans Motwani. HU&M a éliminé tous les bons problèmes!
Jeffε
3
@ user1652: Je ne pense pas que vous allez trouver quelque chose avec plus d'exemples que le livre de Linz. Vous pouvez également jeter un oeil à "Introduction à la théorie informatique" par Daniel Cohen. Il contient de nombreux exemples, mais c'est un livre plus ancien et peut-être pas aussi lisible que Linz.
Kurt
2
@Kurt: Vos commentaires sont trop bons pour être laissés comme de simples commentaires! Pourquoi ne pas les poster comme réponses?
MS Dousti
9

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.

mikero
la source
9

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.

Sylvain
la source
1
Si nous ne parlons que de la théorie des automates, ce doit être le meilleur livre sur le sujet. Je le lis et je l'adore!
Marcos Villagra
5

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

s8soj3o289
la source
5

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

Shambo
la source
5

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.

Lev Reyzin
la source
1

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
subshift
la source
1

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.

Yannis Ntallas
la source
0

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.

guhemama
la source
0

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

Prateek Bhuwania
la source