L ={w∈{a,b}*| 的下推自动机w 包含不同数量的 a 和 b}

Question

我一直在尝试为这种语言找到一个下推自动机，但我无法想出任何令人满意的东西。

我尝试了以下逻辑：对于每次读取，将 A 压入堆栈。对于每个 b 读取，按下 B入栈。但没能成功。

Answer 1

试试这个：

对于每个读取的令牌：

• 如果栈为空或者栈顶与token匹配，则压入token
• 如果堆栈顶部与令牌不匹配，则弹出它。

输入最后：

• 如果堆栈为空，则拒绝
• 如果堆栈不为空，则接受