dfa - DFA 到 PDA 转换

Question

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

任何帮助表示赞赏。

谢谢！

Answer 1

DFA 的 PDA 版本看起来是一样的，只是每个状态转换也不会将任何内容压入堆栈并且不会从堆栈中弹出任何内容。

Answer 2

由于 PDA 是 DFA 的扩展，只有一个附加功能：堆栈。因为 PDA 的转换由三元组（当前状态、输入、堆栈顶部的元素）确定，而 DFA 的转换由元组（当前状态、输入）确定。唯一的区别是堆栈顶部的元素。e您可以通过将元组转换为三元组（空字符串）作为堆栈顶部的元素插入来转换 DFA 的所有转换

并在更改状态后，将e（空字符串）推送到堆栈。

Answer 3

I'm answering this old question just in case someone else looks at it.

The conversions of DFA to PDA can be automated easily by just adding a stack. But there could be possible changes to the semantics of the DFA and after you change it that way manually you could end up in a PDA with less number of states. I faced this problem recently. Its somewhat like this,

In a system (not a compiler or anything like that) the code written earlier was written using an DFA due to some reasons. The transitions occur as the user progress through the code using various functions. After some time a new set of transitions functions arrived which can be used in any order. and also the state after any of these new functions can change back to previous state by one of these functions. The only way to solve this using FST was to add a large number of new states to support this behavior which i a huge amount of work. But instead I just changed from DFA to a PDA. The stack keeps track of the transitions very nicely and the problem is solved with far less number of states. Actually i only had to add N number of states where N is the number of new functions that arrived.

I do not know if someone can automate this kind of a process easily. But there you go, just in case someone is curious about it.

Answer 4

维基百科文章说

下推自动机与有限状态机有两个不同之处：

1. 他们可以使用堆栈的顶部来决定采用哪个转换。
2. 他们可以操作堆栈作为执行转换的一部分。

下推自动机通过按输入信号、当前状态和堆栈顶部的符号索引表来选择转换。这意味着这三个参数完全决定了所选择的过渡路径。有限状态机只查看输入信号和当前状态：它们没有可使用的堆栈。下推自动机添加堆栈作为参数供选择。

...
下推自动机等价于上下文无关文法：对于每一个上下文无关文法，都存在一个下推自动机，使得该文法生成的语言与自动机生成的语言相同，这很容易证明。反之亦然，但更难证明：对于每个下推自动机，都存在一个上下文无关文法，使得自动机生成的语言与文法生成的语言相同。