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.
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.
Odpowiedzi:
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ń:
„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.
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.