Преобразование 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 автоматы добавляют стек в качестве параметра для выбора.

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