在使用 PDA 定义 CFG 或类型 2 语法的转换时，我们需要初始堆栈符号，主要由 Zo 表示。我的疑问是为什么我们需要它，因为最终我们将完全清空堆栈......？？
问问题
909 次
1 回答
2
下推自动机需要初始堆栈符号，因为每次移动都由当前输入符号和堆栈顶部的符号决定。这导致如果堆栈为空，则无法移动。
是的，堆栈可以减少到只有堆栈符号。考虑...
L={ (a^n)(b^n) : n >= 0 }
0我可以为我阅读的每个内容按下 a a，其中 - 顺便说一句 - 其中第一个将是 (q0, a, z)，然后当我阅读我的第一个内容时，b我弹出0s 并且什么也不推回。我知道我已经完成并且当没有输入消耗并且堆栈符号位于堆栈顶部时，语言被接受。
请注意，在上面的转换函数中，第一个移动是由第一个输入和堆栈符号确定的。你能明白没有它你将永远无法开始吗？
于 2015-04-10T18:55:00.670 回答