computation-theory - 下推自动机和算术表达式

Question

我想弄清楚如何在下推自动机中做算术表达式？（PDA）例如 L=W|W=An Bm Cn-m 我想做的是先推 As 然后 pop Bs 然后再 pop As with C 或 Bs 与 C 取决于剩下的内容。例如 aaabbc（推 aaa 然后用 Bs bba 弹出，然后用 C 弹出 A 或用 C 弹出 B，这取决于哪个更大。

Answer 1

对于w语言中的单词，它必须符合n>=m您的定义（否则C^(n-m)是否定的，这是不可能的）。

因此，您的自动机基本上需要：

1. 看到“a”时推入堆栈
2. 看到 'b' 从堆栈中弹出
3. 看到'c'时从堆栈中弹出。

另外，一些重要的问题：

• 看到“新”角色时，您需要在不同状态之间移动。
• 您的自动机应该接受w=eps（空字）。
• w=a^b b^n也是在语言中，请确保您注意这一点。

我希望我给了你足够好的线索来自己解决它。

祝你好运！