Хопкрофт Д., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений

2-е изд. Пер. с англ. — Москва; Санкт Петербург; Киев: Вильямс, 2002. — 528 с.: ил. — ISBN 5-8459-0261-4.Книга известных американских ученых посвящена теории автоматов и соответствующих формальных языков и грамматик - как регулярных, так и контекстно-свободных. Во второй части рассматриваются различные машины Тьюринга, при помощи которых формализуются понятия разрешимых и неразрешимых проблем, а также определяются функции временной и емкостной оценки сложности алгоритмов. Изложение ведется строго, но доступно, и сопровождается многочисленными примерами, а также задачами для самостоятельного решения.
Книга будет полезна читателям различных категорий - студентам, аспирантам, научным сотрудникам, преподавателям высших учебных заведений, а также всем, кто интересуется математическими основами современной вычислительной техники.Автоматы: методы и понятия.
Конечные автоматы.
Регулярные выражения и языки.
Свойства регулярных языков.
Контекстно-свободные грамматики и языки.
Автоматы с магазинной памятью.
Свойства контекстно-свободных языков.
Введение в теорию машин Тьюринга.
Неразрешимость.
Труднорешаемые проблемы.
Дополнительные классы проблем.