我可以将两个符号压入下推自动机的堆栈吗？
can i push two symbols to the stack of a pushdown automata?
我想知道对于给定的下推自动机，初始符号或 Z0 是 y，当我在转换期间从字符串链中读取 'a' 时，我是否可以堆叠两个 X？
假设我有一个转换函数，如下所示：(s1, a, y) -> (s2, e, xxy)。这样的过渡有效吗？如果仍然不清楚，这里有一个绘画图像可以更好地理解。
其中 Z0 = Y
这实际上是一个关于您如何定义 PDA 的问题——您选择使用什么约定。通常，我认为惯例是一个转换推动一个符号。但是，允许推送任意字符串不会增加 PDA 模型的功能（尽管它可以减少所需状态的数量）。要看到这一点，请使用任何将长度大于 1 的字符串压入堆栈的 PDA。通过引入具有 empty/lambda/epsilon 转换的附加状态以一次压入一个符号，可以将此 PDA 转换为将长度最多为一个的字符串压入堆栈的 PDA。这甚至不会将 DPDA 变成 NPDA，因为如果在转换之前是这种情况，那么在新的 PDA 中的任何给定时间仍然最多只能进行一次转换。
事实上，用于显示 PDA 可以接受 CFG 语言的结构明确依赖于能够在一次转换中推送任意长度的字符串。该构造通过推动开始符号然后不确定地推动非终端的产生式来工作。由于产生式的 RHS 通常长于一个符号，因此如果生成的 PDA 必须为每个产生式都具有单独的状态路径，则构造将更加丑陋。通过允许推入任意长度的字符串，该构造为任何 CFG 生成一个双态 NPDA。
我想知道对于给定的下推自动机，初始符号或 Z0 是 y，当我在转换期间从字符串链中读取 'a' 时，我是否可以堆叠两个 X？
假设我有一个转换函数，如下所示：(s1, a, y) -> (s2, e, xxy)。这样的过渡有效吗？如果仍然不清楚，这里有一个绘画图像可以更好地理解。
其中 Z0 = Y
这实际上是一个关于您如何定义 PDA 的问题——您选择使用什么约定。通常，我认为惯例是一个转换推动一个符号。但是，允许推送任意字符串不会增加 PDA 模型的功能（尽管它可以减少所需状态的数量）。要看到这一点，请使用任何将长度大于 1 的字符串压入堆栈的 PDA。通过引入具有 empty/lambda/epsilon 转换的附加状态以一次压入一个符号，可以将此 PDA 转换为将长度最多为一个的字符串压入堆栈的 PDA。这甚至不会将 DPDA 变成 NPDA，因为如果在转换之前是这种情况，那么在新的 PDA 中的任何给定时间仍然最多只能进行一次转换。
事实上，用于显示 PDA 可以接受 CFG 语言的结构明确依赖于能够在一次转换中推送任意长度的字符串。该构造通过推动开始符号然后不确定地推动非终端的产生式来工作。由于产生式的 RHS 通常长于一个符号，因此如果生成的 PDA 必须为每个产生式都具有单独的状态路径，则构造将更加丑陋。通过允许推入任意长度的字符串，该构造为任何 CFG 生成一个双态 NPDA。