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

Question

我一直在为这个自动机构建转换函数。

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

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

Answer 1

不要在每次遇到 b 时将 0 压入堆栈。相反，每次遇到 b 并且堆栈为空或堆栈顶部为 0 时，将 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

堆栈为空，因此我们接受此字符串。