我可以将两个符号推到推倒式自动机的堆栈中吗？

Question

我想知道，对于一个给定的推倒式自动机，初始符号或Z0是y，当我在过渡期间从字符串链中读出'a'时，我是否可以堆叠两个X？

假设我有一个过渡函数如下。(s1, a, y) -> (s2, e, xxy). 这样的过渡是否有效？为了更好的理解，这里有一个画像，以防还是不清楚。

其中Z0=Y

Answer 1

这其实是一个你如何定义PDA的问题--你选择使用什么约定。通常情况下，我认为约定俗成的做法是，一次过渡推送一个符号。然而，允许任意字符串被推送并不会给PDA模型增加任何力量（尽管它可以减少所需状态的数量）。为了看清这一点，拿任何一个将长度大于1的字符串推送到堆栈上的PDA来说。这个PDA可以通过引入额外的状态，用emptylambdaepsilon转换来将长度最多为1的字符串推到堆栈上，从而转变为一个PDA。这甚至没有把DPDAs变成NPDAs，因为在新的PDA中，在任何给定的时间仍然只有一个过渡可能，如果在转换之前是这样的话。

事实上，用于证明PDAs可以接受CFG语言的结构明确地依赖于能够在一次转换中推送任意长度的字符串。该结构的工作原理是推送起始符号，然后不确定地推送非终结符的乘积。由于产物的RHS通常比一个符号长，如果产生的PDA必须为每个产物提供单独的状态路径，那么这种结构将变得更加丑陋。通过允许推送任意长度的字符串，该构造为任何CFG生成了一个双状态的NPDA。