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

Question

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

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

Answer 1

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

Для набора наборов задач на автоматах вместе с решениями, ознакомьтесь со вводным курсом Стэнфорда по теории вычислений. Наборы задач 5, 6 и 7 прямо говорят об автоматах (машинах с конечными числами, машинами с понижением и Тьюринга) вместе с эквивалентными представлениями (регулярные выражения и контекстно-свободные грамматики).

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