Преобразование DFA в PDA

Question

Я ищу алгоритм для преобразования детерминированных конечных автоматов в автоматы Push Down.

Любая помощь приветствуется.

Спасибо!

Answer 1

Версия DFA для КПК выглядела бы одинаково, за исключением того, что каждый переход состояния также не помещал в стек ничего и не выталкивал из стека.

Answer 2

Поскольку КПК является расширением DFA с помощью только одной дополнительной функции: стек. Поскольку переход PDA определяется тройкой (текущее состояние, вход, элемент в верхней части стека), а переход DFA определяется кортежем (текущее состояние, вход). И единственное отличие - это элемент в верхней части стека. Вы можете преобразовать все переходы DFA, преобразовав кортеж в тройной, e (пустая строка), вставленный как элемент в верхней части стека

И после изменения состояния нажмите e (пустая строка) в стек.

Answer 3

Я отвечаю на этот старый вопрос на тот случай, если кто-то еще посмотрит на него.

Преобразование DFA в PDA можно легко автоматизировать, просто добавив стек. Но могут быть возможные изменения в семантике DFA, и после того, как вы измените его таким образом вручную, вы можете оказаться в КПК с меньшим количеством состояний. Я столкнулся с этой проблемой недавно. Это примерно так,

В системе (не компилятор или что-то в этом роде) код, написанный ранее, был написан с использованием DFA по некоторым причинам. Переходы происходят по мере прохождения пользователем кода через различные функции. Через некоторое время появился новый набор функций переходов, который можно использовать в любом порядке. а также состояние после того, как любая из этих новых функций может вернуться в предыдущее состояние с помощью одной из этих функций. Единственный способ решить эту проблему с помощью FST - добавить большое количество новых состояний для поддержки этого поведения, что требует огромного количества работы. Но вместо этого я просто перешел с DFA на КПК. Стек отслеживает переходы очень хорошо, и проблема решается с гораздо меньшим количеством состояний. На самом деле мне нужно было только добавить N количество состояний, где N - количество новых функций, которые поступили.

Я не знаю, может ли кто-нибудь легко автоматизировать этот процесс. Но вот, пожалуйста, на всякий случай, если кому-то это интересно.

Answer 4

В статье Википедии говорится

Автоматы Pushdown отличаются от конечных конечные автоматы двумя способами:

1. Они могут использовать вершину стека, чтобы решить, какой переход к брать.
2. Они могут манипулировать стеком как часть выполнения перехода.

Автоматы пушдауна выбирают переход путем индексации таблицы по входному сигналу, текущее состояние и символ на вершина стека. Это означает, что эти три параметра полностью определить путь перехода, который выбран. Конечные автоматы просто посмотрите на входной сигнал и текущее состояние: у них нет стека работать с. Pushdown автоматы добавить стек как параметр для выбора.

...
Pushdown автоматы эквивалентны контекстно-свободные грамматики: для каждого контекстно-свободная грамматика, существует автомат, такой, что язык, созданный грамматикой идентичен сгенерированным языком автоматом, который легко доказать. Обратное правда, хотя труднее доказать: за каждое нажатие автомат существует без контекста грамматика такая, что язык генерируется автоматом идентичен сгенерированным языком по грамматике.