Где я могу найти образцы автоматов и машин Тьюринга?[закрыто]

Question

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

Где я могу найти больше?Любой другой ресурс с примерами машин Тьюринга, показанными в виде графиков с переходами, также был бы полезен.

Answer 1

"Решение задач в автоматах, языках и сложности" - фантастический учебник для всего, что связано с...все, что есть в его названии.Среди прочего, вы можете найти кучу примеров DFA / NFA / КПК / TMS для самых разных целей, и они научат вас множеству приемов их построения.

Редактировать:в вашей первой ссылке все время говорится о "недетерминированных NPDA" и "детерминированных NPDA".Я пишу эту правку только для того, чтобы удовлетворить свое желание осудить подобные плеоназмы и оксимору :)

Answer 2

Попробуйте превосходную книгу Майкла Сипсера "Введение в теорию вычислений".Все автоматы и машины Тьюринга представлены в виде диаграмм состояний с достаточным текстовым пояснением, которое поможет вам интерпретировать и реализовать их.

Это был текст нашего курса в университете около 4 лет назад, как раз перед выходом 2-го издания;это был настоящий рок, я от всей души рекомендую его!