DPDA自动规则

Question

我无法理解VS DPDA NPDA之间的区别，我认为它会像从多个选项，可采取到下一个状态

的状态这

NPDA- DPDA-从状态，只有1路，可采取的下一个状态

..但有2个关于DPDA，我不能得到

..per维基百科 黑白理解规则

的第一条规则：

• q是一个国家，一个是字母符号，x是堆栈符号

什么是“至多有一个元素”的意思

我不知道第二条规则是什么意思。

请问有人可以将此翻译成纯英文。我会很感激。

Answer 1

对于第一条规则，“至多有一个元素”意味着对于特定的输入和堆栈符号只有一个delta转换（delta转换正式作为PDA的集合对待）。换句话说，如果在堆栈顶部有输入，输入就没有多个状态了。

如您所述，“DPDA-从一个状态开始，只有一条路径可以进入下一个状态。”这条规则是表示只能采取一条路径的正式方式。

违反规则1可能会在相同的状态下使用相同的输入符号和堆栈符号指定两个增量转换。例如，从状态q可能有两个转换，每个需要堆栈上的b和a作为输入，但转到不同的状态。这不会是DPDA。

第二条规则规定，如果堆栈符号下的空字符串存在delta转换，那么堆栈符号下的字母表中的任何字母都不会有delta转换。

这意味着如果你允许一个特定的堆栈符号在没有任何输入的状态下被弹出，你不能允许它也以相同的输入状态弹出。

违反规则2可能会允许从堆栈中弹出a s，但不会在2个状态之间进行任何输入，但也允许从b作为输入弹出堆栈中的a。