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

32

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.

użytkowników1652
źródło

Odpowiedzi:

35

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

Sadeq Dousti
źródło
8
Drugi Sipster. Używam tego do mojego kursu.
Dave Clarke,
2
Całe lato spędziłem na problemach ze starej książki HU. Zabawne czasy ...
Suresh Venkat
8
Zdecydowanie wolę Hopcroft i Ullman bez Motwani. HU&M wyjął wszystkie dobre problemy!
Jeffε
3
@ user1652: Nie sądzę, że znajdziesz coś z większą liczbą przykładów niż książka Linza. Możesz także rzucić okiem na „Wprowadzenie do teorii komputerów” Daniela Cohena. Ma wiele przykładów, ale jest starszą książką i może nie tak czytelną jak Linz.
Kurt
2
@Kurt: Twoje komentarze są zbyt piękne, aby pozostawić je jako komentarze! Dlaczego nie opublikować ich jako odpowiedzi?
MS Dousti
9

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.

mikero
źródło
9

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

Sylvain
źródło
1
Jeśli mówimy tylko o teorii automatów, to musi to być najlepsza książka na ten temat. Czytam i kocham!
Marcos Villagra
5

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

s8soj3o289
źródło
5

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

Shambo
źródło
5

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.

Lew Reyzin
źródło
1

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
subshift
źródło
1

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

Yannis Ntallas
źródło
0

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.

guhemama
źródło
0

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

Prateek Bhuwania
źródło