Где я могу найти образцы автоматов и машин Тьюринга?
Я учусь на автоматном тесте по курсу, который в значительной степени основан на jflap. Проблема в том, что у нас не так много документации, и примеры автоматов, которые я нашел на jlap вроде этого и этого, недостаточны для подготовки к предстоящему тесту.
Где я могу найти больше? Любой другой ресурс с примерами машин Тьюринга, показанных в виде графиков с переходами, также будет полезен.
2 ответа
"Решение проблем в автоматах, языках и сложности" - фантастический учебник для всего, что связано с... чем угодно в его названии. Среди прочего, вы можете найти множество примеров DFA /NFA /PDA /TM для всех видов вещей, и они научат вас многим методам их создания.
Изменить: эта ваша первая ссылка продолжает говорить о "недетерминированных NPDA" и "детерминированных NPDA". Я пишу эту редакцию только для того, чтобы удовлетворить мое желание осудить такие плеоназмы и оксиморы:)
Попробуйте отличную книгу Майкла Сипсера "Введение в теорию вычислений". Автоматы и машины Тьюринга представлены в виде диаграмм состояний с достаточным количеством текстовых пояснений, чтобы помочь вам интерпретировать и реализовывать их.
Это был текст нашего курса в Uni около 4 лет назад, перед выходом второго издания; это был настоящий рок, я от всей души рекомендую его!