Книга известных американских ученых посвящена теории автоматов и соответст- вующих формальных языков и грамматик - как регулярных, так и контекстно- свободных. Во второй части рассматриваются различные машины Тьюринга, при помо- щи которых формализуются понятия разрешимых и неразрешимых проблем, а также определяются функции временной и емкостной оценки сложности алгоритмов. Изложе- ние ведется строго, но доступно, и сопровождается многочисленными примерами, а также задачами для самостоятельного решения. Книга будет полезна читателям различных категорий - студентам, аспирантам, науч- ным сотрудникам, преподавателям высших учебных заведений, а также всем, кто интересуется математическими основами современной вычислительной техники. Оглавление Предисловие 14 ГЛАВА 1. Автоматы: методы и понятия 17 ГЛАВА 2. Конечные автоматы 53 ГЛАВА 3. Регулярные выражения и языки 101 ГЛАВА 4. Свойства регулярных языков 143 ГЛАВА 5. Контекстно-свободные грамматики и языки 185 ГЛАВА 6. Автоматы с магазинной памятью 233 ГЛАВА 7. Свойства контекстно-свободных языков 269 ГЛАВА 8. Введение в теорию машин Тьюринга 319 ГЛАВА 9. Неразрешимость 377 ГЛАВА 10. Труднорешаемые проблемы 423 ГЛАВА 11. Дополнительные классы проблем 481 Предметный указатель 523