Книги по теории автоматов для самостоятельной работы

Мне нужна книга по теории конечных автоматов с множеством примеров, которые я могу использовать для самостоятельного изучения и подготовки к экзаменам.

Классическая ссылка - « Введение в теорию автоматов, языков и вычислений » (Хопкрофт, Мотвани и Уллман). Некоторые люди также рекомендуют более старые « Формальные языки и их отношение к автоматам » (Хопкрофт и Уллман).

Мне, однако, нравится « Введение в теорию вычислений » (автор Sipser). Это очень хорошо написано, и это относительно новая книга.

У меня есть слабость к автоматам и вычислимости Декстера Козена ( оглавление и примеры глав [PS]). Это довольно тщательно и охватывает некоторые действительно интересные продвинутые темы. Доказательства формальны и явны, а обозначения и форматирование прекрасны. Самое главное, что упражнения отличные, поэтому в зависимости от уровня ваших экзаменов это будет хороший учебный материал.

Больше всего я использую в своих курсах « Элементы теории автоматов » Жака Сакаровича, издательство Cambridge University Press, 2009. Его область может немного отличаться от других, так как он также широко охватывает алгебраические аспекты, формальные степенные ряды, и трансдукции. И есть много упражнений.

«Прикладная комбинаторика в словах», Lothaire, 2004

Далеко и далеко мой любимый. Множество примеров, а также от абсолютных основ до целого ряда довольно интересных автоматических приложений, таких как автоматическое распознавание речи с взвешенными датчиками конечных состояний и темы биоинформатики.

Лучше всего, что это бесплатно для скачивания, а также включает в себя наборы решений:

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

«Решение проблем в автоматах, языках и сложности» Ду-Ко - одна из моих любимых после Sipser, HU и Kozen. Он содержит много решений для проблем Козена и sipser с многочисленными примерами и соответствующими упражнениями. Особенно полезно для подготовки к экзамену.

Я не уверен, что это лучшая книга для подготовки к экзаменам, но книга

Конечные автоматы; Поведение и синтез Б.А. Трахтенброта и Я. М. Барздиньо

довольно хорошо. Он имеет удивительное количество отличных результатов, которые я нашел особенно полезными в исследованиях.

Введение в языки и теорию вычислений

Джон К. Мартин

Я очень рекомендую эту книгу для начинающих, и это идеальный выбор для тех, кто ищет много примеров.

Мне нравятся следующие заметки Джаркко Кари: http://users.utu.fi/jkari/automata/

Краткое описание курса:

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

Есть также элементы теории вычислений Х. Льюиса и К. Пападимитриу. Это хорошо написанное введение в теорию автоматов.

Понимание вычислений

От простых машин к невозможным программам

Он охватывает много вещей, включая теорию автоматов. Примеры представлены в Ruby, и их довольно легко понять. Вам может понадобиться другая книга, если вы хотите углубиться в теорию, но эта книга отлично подходит для изучения основ.

«Формальные языки и теория автоматов» А. А. Пунтамбекара - лучшая книга для решенных примеров. Большая часть книги содержит только решенные примеры и немного теории. Хорошо сдавать экзамены.