Książki z teorii automatów do samodzielnego studiowania

Potrzebuję skończonej książki z teorią automatów z wieloma przykładami, które mogę wykorzystać do samodzielnej nauki i przygotowania się do egzaminów.

Klasyczne odniesienie to „ Wprowadzenie do teorii automatów, języków i obliczeń ” (autor: Hopcroft, Motwani i Ullman). Niektóre osoby polecają również znacznie starsze „ Języki formalne i ich związek z automatami ” (autorstwa Hopcroft i Ullman).

Lubię jednak „ Wprowadzenie do teorii obliczeń ” (autor: Sipser). Jest bardzo dobrze napisany i jest stosunkowo nową książką.

Mam słabość do automatów i obliczalności autorstwa Dextera Kozen'a ( spis treści i przykładowe rozdziały [PS]). Jest dość dokładny i obejmuje kilka naprawdę interesujących zaawansowanych tematów. Dowody są formalne i wyraźne, a notacja i formatowanie są piękne. Co najważniejsze, ćwiczenia są doskonałe, więc w zależności od poziomu egzaminów będzie to dobry materiał do nauki.

Ten, z którego najczęściej korzystam na kursach, to Elementy teorii automatów Jacquesa Sakarovitcha, Cambridge University Press, 2009. Jego zakres może być nieco inny niż innych, ponieważ obejmuje również aspekty algebraiczne, formalne serie potęg, i transdukcje. I jest wiele ćwiczeń.

„Applied Combinatorics on Words”, autor: Lothaire, 2004

Jest zdecydowanie moim ulubionym. Mnóstwo przykładów, a także gromadzi się od absolutnych podstaw aż do całkiem interesujących aplikacji automatów, takich jak automatyczne rozpoznawanie mowy z ważonymi przetwornikami skończonymi i tematy w bioinformatyce.

Co najlepsze, można go bezpłatnie pobrać, a także zawiera zestawy rozwiązań:

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

„Rozwiązywanie problemów w automatach, językach i złożoności” autorstwa Du-Ko jest jednym z moich ulubionych po Sipserze, HU i Kozen. Zawiera wiele rozwiązań * problemów Kozen i Sipser z licznymi przykładami i powiązanymi ćwiczeniami. Szczególnie przydatny do przygotowania do egzaminu.

Nie jestem pewien, czy to najlepsza książka do przygotowania się do egzaminów, ale książka

Automaty skończone; Zachowanie i synteza BA Trakhtenbrota i Ya. M. Barzdinʹ

jest całkiem dobry. Ma zaskakującą liczbę świetnych wyników, które okazały się szczególnie pomocne w badaniach.

Wprowadzenie do języków i teoria obliczeń

John C. Martin

Bardzo polecam tę książkę początkującym i jest to idealny wybór dla kogoś, kto szuka wielu przykładów.

Lubię następujące wykłady Jarkko Kari: http://users.utu.fi/jkari/automata/

Krótki zarys kursu:

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

Istnieją również elementy teorii obliczeń H.Lewisa i C.Papadimitriou. To dobrze napisane wprowadzenie do teorii automatów.

Zrozumienie obliczeń

Od prostych maszyn do niemożliwych programów

Obejmuje wiele rzeczy, w tym teorię automatów. Przykłady są przedstawione w języku Ruby i są dość łatwe do zrozumienia. Możesz potrzebować innej książki, jeśli chcesz zagłębić się w teorię, ale ta świetnie nadaje się do nauki podstaw.

„Formal Languages ​​And Automata Theory” AA Puntambekar to najlepsza książka dla rozwiązanych przykładów. Większość książki zawiera tylko rozwiązane przykłady i mało teorii. Dobrze zdać egzaminy.