Я пытаюсь создать симулятор Pu-1006 * -Down Automata (PDA) с Python, и, как следует из заголовка, я натолкнулся на стену о том, как пройти его с помощью предоставленной строки. У меня есть реализованная таблица переходов и функции для получения переходов по состоянию и символу. Вопрос заключается в том, как обойти таблицу, когда переход имеет несколько состояний для заданного символа в алфавите. Например, если начальное состояние Q1 получает символ «0» из строки «0011», оно может перейти либо в Q2, либо в Q3. Таким образом, мне нужно будет проверить два пути и пройти их по строке. Если «путь» Q2 не принимает строку, то мне нужно будет «go вернуться» к Q3 и попробовать этот путь. Проблема заключается в том, чтобы отслеживать состояние этих вилок и возвращаться к ним, когда другой путь не принимает строку.
Я хотел бы реализовать это с помощью рекурсии, но мне нужно будет отследить три вещи: список состояний, которые необходимо пройти, строку на каждом из этих путей и стек КПК. Мне также нужен был бы способ вернуться к предыдущему пункту с неизменными переменными.
Любые предложения о том, как подойти к этому, будут весьма уместны.