我的朋友问我一个关于下推自动机的问题。蕉麻。我正在研究一些类似的问题，但所有问题都包含偶数，就像 0^a 1^a 但现在我有 3 个值。我找到了一个例子，但我无法将我的问题转换为这个。
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
我怎样才能转换蕉麻？
我知道这已经有一段时间了，但以防万一有人在寻找类似的问题......为什么要重新讨论这个？
基本思想是这样的：下推自动机有一个堆栈。因此，尽可能多地读取 a，每次都将一个额外的“a”推入堆栈。然后读取 b 并进入下一个状态。
现在再次读取尽可能多的 a，再次将所有 a 压入堆栈。然后读取 ac 并进入下一个状态。
现在，只要您正在查看堆栈顶部的“a”，就可以阅读 a。当您查看堆栈底部符号时，转换到最终接受状态。
如果您有更多的 a，则没有转换并且您的字符串不被接受（您还没有完成阅读，并且您无处可去，因此您“崩溃”了机器）。否则，如果您在之前的状态中用完了 a，您永远不会进入最终状态，并且您的字符串不会被接受。只有当您只读取与前两次一样多的 a 时，您才会最终处于接受状态，不再需要读取输入，并且字符串被接受。