Buku-buku tentang teori automata untuk belajar sendiri

Saya memerlukan buku teori automata terbatas dengan banyak contoh yang dapat saya gunakan untuk belajar mandiri dan untuk mempersiapkan ujian.

Referensi klasik adalah " Pengantar Teori Automata, Bahasa dan Komputasi " (oleh Hopcroft, Motwani, dan Ullman). Beberapa orang juga merekomendasikan " Bahasa Formal dan Hubungannya dengan Automata " yang jauh lebih tua (oleh Hopcroft dan Ullman).

Saya, bagaimanapun, menyukai " Pengantar Teori Komputasi " (oleh Sipser). Ini ditulis dengan sangat baik, dan merupakan buku yang relatif baru.

Saya memiliki titik lemah untuk Automata & Computability oleh Dexter Kozen ( daftar isi dan bab-bab sampel [PS]). Ini cukup menyeluruh dan mencakup beberapa topik lanjutan yang sangat menarik. Buktinya formal dan eksplisit dan notasi serta formatnya bagus. Yang paling penting, latihan ini sangat baik, jadi tergantung pada tingkat ujian Anda, itu akan menjadi bahan belajar yang baik.

Yang paling sering saya gunakan untuk mata kuliah saya adalah Elements of Automata Theory oleh Jacques Sakarovitch, Cambridge University Press, 2009. Cakupannya mungkin sedikit berbeda dari yang lain, karena juga banyak membahas aspek aljabar, seri kekuatan formal, dan transduksi. Dan ada banyak latihan.

"Combinatorics Terapan pada Kata", oleh Lothaire, 2004

Jauh dan jauh favorit saya. Banyak contoh, dan juga membangun dari dasar-dasar absolut sampai ke beberapa aplikasi automata yang cukup menarik seperti Pengenalan Wicara Otomatis dengan Transduser Negara-Berbobot Hingga, dan topik dalam bioinformatika.

Yang terbaik dari semuanya, gratis untuk mengunduh, dan juga termasuk rangkaian solusi:

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

"Pemecahan Masalah dalam Automata, Bahasa, dan Kompleksitas" oleh Du-Ko adalah salah satu favorit saya setelah Sipser, HU dan Kozen. Ini berisi banyak solusi untuk masalah * Kozen dan sipser dengan banyak contoh dan latihan terkait. Berguna khusus untuk persiapan ujian.

Saya tidak yakin ini adalah buku terbaik untuk persiapan ujian, tetapi buku itu

Automata terbatas; Perilaku dan Sintesis oleh BA Trakhtenbrot dan Ya. M. Barzdinʹ

cukup bagus Ini memiliki sejumlah hasil luar biasa yang saya temukan sangat membantu dalam penelitian.

Pengantar bahasa dan Teori perhitungan

John C. Martin

Saya sangat merekomendasikan buku ini untuk pemula dan ini adalah pilihan yang sempurna untuk seseorang yang mencari banyak contoh.

Saya menikmati catatan kuliah berikut oleh Jarkko Kari: http://users.utu.fi/jkari/automata/

Garis besar kursus singkat:

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

Ada juga Elemen Teori Teori Komputasi oleh H.Lewis dan C.Papadimitriou. Ini adalah pengantar yang ditulis dengan baik untuk teori automata.

Memahami Komputasi

Dari Mesin Sederhana ke Program Tidak Mungkin

Itu mencakup banyak hal, yang termasuk teori automata. Contoh-contoh disajikan dalam Ruby, dan mereka cukup mudah dimengerti. Anda mungkin perlu buku lain jika ingin mempelajari lebih dalam tentang teori, tetapi buku ini bagus untuk mempelajari dasar-dasarnya.

"Teori Bahasa Resmi dan Automata" oleh AA Puntambekar adalah buku terbaik untuk contoh-contoh terselesaikan. Sebagian besar buku hanya berisi contoh-contoh yang dipecahkan dan sedikit teori. Baik untuk lulus ujian.