Bücher zur Automatentheorie zum Selbststudium

Ich brauche ein Buch zur endlichen Automatentheorie mit vielen Beispielen, die ich zum Selbststudium und zur Prüfungsvorbereitung verwenden kann.

Die klassische Referenz ist " Introduction To Automata Theory, Languages ​​and Computation " (von Hopcroft, Motwani und Ullman). Einige Leute empfehlen auch die viel älteren " Formalen Sprachen und ihre Beziehung zu Automaten " (von Hopcroft und Ullman).

Mir gefällt jedoch " Introduction to the Theory of Computation " (von Sipser). Es ist sehr gut geschrieben und ein relativ neues Buch.

Ich habe ein Faible für Automata & Computability von Dexter Kozen ( Inhaltsverzeichnis und Beispielkapitel [PS]). Es ist ziemlich gründlich und deckt einige wirklich interessante fortgeschrittene Themen ab. Die Beweise sind formal und explizit und die Notation und Formatierung sind sehr schön. Am wichtigsten ist, dass die Übungen hervorragend sind. Je nach Prüfungsniveau ist es also ein gutes Lernmaterial.

Diejenige, die ich für meine Kurse am häufigsten benutze, ist Elements of Automata Theory von Jacques Sakarovitch, Cambridge University Press, 2009. Ihr Umfang unterscheidet sich möglicherweise etwas von dem der anderen, da sie auch algebraische Aspekte, formale Potenzreihen, und Transduktionen. Und es gibt viele Übungen.

"Angewandte Kombinatorik an Wörtern", von Lothaire, 2004

Ist bei weitem mein Favorit. Viele Beispiele, die von den absoluten Grundlagen bis hin zu einigen interessanten Automatenanwendungen wie der automatischen Spracherkennung mit gewichteten Finite-State-Wandlern und Themen der Bioinformatik reichen.

Das Beste ist, dass es kostenlos heruntergeladen werden kann und auch Lösungssätze enthält:

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

"Problemlösung in Automaten, Sprachen und Komplexität" von Du-Ko ist einer meiner Favoriten nach Sipser, HU und Kozen. Es enthält viele Lösungen für die * rden Probleme von Kozen und Sipser mit zahlreichen Beispielen und zugehörigen Übungen. Besonders nützlich für die Prüfungsvorbereitung.

Ich bin mir nicht sicher, ob dies das beste Buch ist, um sich auf Prüfungen vorzubereiten, aber das Buch

Endliche Automaten; Verhalten und Synthese von BA Trakhtenbrot und Ya. M. Barzdinʹ

ist ziemlich gut. Es hat eine überraschende Anzahl großartiger Ergebnisse, die ich in der Forschung als besonders hilfreich empfunden habe.

Einführung in Sprachen und die Theorie der Berechnung

John C. Martin

Ich kann dieses Buch nur Anfängern empfehlen und es ist die perfekte Wahl für jemanden, der nach vielen Beispielen sucht.

Ich genieße die folgenden Skriptum von Jarkko Kari: http://users.utu.fi/jkari/automata/

Kurze Kursbeschreibung:

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

Es gibt auch Elemente der Berechnungstheorie von H. Lewis und C. Papadimitriou. Es ist eine gut geschriebene Einführung in die Automatentheorie.

Grundlegendes zur Berechnung

Von einfachen Maschinen zu unmöglichen Programmen

Es deckt eine Menge Dinge ab, einschließlich der Automatentheorie. Die Beispiele sind in Ruby dargestellt und recht einfach zu verstehen. Sie brauchen vielleicht ein anderes Buch, wenn Sie tiefer in die Theorie eintauchen möchten, aber dieses ist großartig, um die Grundlagen zu lernen.

"Formale Sprachen und Automatentheorie" von AA Puntambekar ist das beste Buch für gelöste Beispiele. Der größte Teil des Buches enthält nur gelöste Beispiele und wenig Theorie. Es ist gut, die Prüfungen zu bestehen.