pushdown-automaton - (a^nb^n)^mc^m 的下推自动机

Question

我一直在为这个自动机构建转换功能。

我想我应该为每个 a 堆叠一个 1 并为每个 b 取消堆叠它

c 的数量等于 ab 对的数量，所以我认为我应该为遇到的每个 b 堆叠一个 0。问题是：我如何同时取消堆叠 1 和添加 0？

Answer 1

0每次遇到 a 时不要将 a 压入堆栈b。相反，0每次遇到 ab并且堆栈为空或堆栈顶部为 a时，将 a 压入堆栈0。

因此，使用您的命名法aabbabcc：

read a push 1
read a push 1
read b pop 1
read b pop 1
stack is empty so push 0
read a push 1
read b pop 1 
top of stack is 0 so push 0
read c pop 0
read c pop 0

Stack 是空的，所以我们接受这个字符串。