DFA到PDA的转换

Question

我正在寻找算法将确定性有限自动机转换为按下自动机。

任何帮助表示赞赏。

谢谢！

Answer 1

的wikipedia article说

下推自动从有限 状态机有两点不同：

1. 他们可以使用堆栈的顶部，以决定哪些过渡到 服食。
2. 他们可以操作堆栈作为执行转换的一部分。

下推自动选择由输入信号， 当前状态，并且在顶部 堆叠的符号索引的表的过渡 。这意味着 这三个参数完全确定 选择的转换路径为 。有限状态机只需 看看输入信号和 目前的状态：他们没有任何堆栈可以与 一起工作。下推自动机添加 堆栈作为参数供您选择。

...
下推自动机相当于 上下文无关文法：每 上下文无关文法，存在 下推自动机，使得由语法产生的 语言是 相同与所产生的语言 由自动机，这很容易 证明。的情况正好相反，虽然 更难证明：每下推自动机 存在一个上下文 语法，使得由自动机所产生的语言 是 与语言相同由语法产生的 。

Answer 2

DFA的PDA版本看起来是一样的，除了每个状态转换也不会在堆栈上压入任何东西，并且不会弹出堆栈。

Answer 3

由于PDA是DFA的扩展，只有一个附加功能：堆栈。 由于PDA的转换是由三元组（当前状态，输入，堆栈顶部的元素）决定的，而DFA的转换由元组（当前状态，输入）确定。唯一的区别是堆栈顶部的元素。您可以通过在堆栈

的顶部转化插入作为元素的元组三，e（空字符串）和更改后的状态DFA的所有过渡转换，推动e（空字符串）堆栈。

Answer 4

我回答这个老问题，以防别人看着它。

只需添加一个堆栈即可轻松实现DFA到PDA的转换。但是可能会对DFA的语义进行更改，并且在您以手动方式更改该方法后，可能会以较少的状态结束于PDA。我最近面临这个问题。它有点像这样，

在一个系统（不是编译器或类似的东西）中，之前编写的代码是由于某些原因使用DFA编写的。转换发生在用户使用各种功能通过代码进行时。经过一段时间后，一组新的过渡功能到达，可以按任何顺序使用。并且这些新功能中的任何一个之后的状态可以通过这些功能之一改回到之前的状态。使用FST解决这个问题的唯一方法是添加大量的新状态来支持这种行为，这是我的一大笔工作。但是，我只是从DFA更改为PDA。堆栈非常好地跟踪转换，问题可以通过少得多的状态来解决。实际上，我只需要添加N个状态，其中N是到达的新功能的数量。

我不知道是否有人可以轻松自动化这种过程。但是，你去了，以防万一有人好奇它。