Конечные автоматы, автоматы выталкивания и примеры машины Тьюринга

Question

Я ищу подходящий источник конечных автоматов, автоматов выталкивания и примеров задач машины Тьюринга (для решения вручную, вручную).

Я искал вокруг, но не нашел ничего особенного, поэтому мне интересно, есть ли у кого-то хорошие примеры. Заранее спасибо.

Answer 1

Ваш лучший выбор может заключаться в том, чтобы получить книгу по этой теме, такую ​​как Introduction to the Theory of Computation, Third Edition от Michael Sipser, а затем выполнить упражнения.

Для коллекции комплектов задач на автоматах, а также решениях, проверьте Stanford's introductory course in the theory of computation. Задача Наборы 5, 6 и 7 прямо говорят о автоматах (конечные, pushdown и машины Тьюринга), а также эквивалентные представления (регулярные выражения и контекстно-свободные грамматики).

Надеюсь, это поможет!