pushdown-automaton - 具有不相等元素的下推自动化

Question

有一种语言 L = {0,1}^* 问题是 1 和 0 不应该是相等的数字。我如何在 PDA 自动机中呈现它？

提前致谢！

Answer 1

PDA 可以读取输入、压入堆栈以及从堆栈中弹出。在尝试设计自动机，尤其是 PDA 和 TM 时，我喜欢将输入字符串想象成一排排长长的彩色弹珠或筹码在桌子上。那么问题是，仅使用一个筹码并从左到右拾取筹码，您如何判断一排筹码是否有不同数量的红色筹码和蓝色筹码？

一种方法如下。当你拿起一个弹珠时，看看堆栈。如果堆栈是空的或顶部有相同颜色的筹码，请将筹码放下。如果最上面的筹码有不同的颜色，请将您捡起的筹码和堆栈中最上面的筹码扔进袋子里。继续，直到你拿起所有的筹码。现在看看堆栈。如果堆栈为空，则意味着您必须扔掉相同数量的红色和蓝色筹码。如果你有一些筹码在筹码中，这意味着有一些筹码你不能扔掉。事实上，剩余筹码的颜色告诉你哪种筹码更多。