下推自动机（a^x b a^y c a^x + y）

Question

我的朋友问我一个关于下推自动机的问题。 abacaa。我正在查看一些类似的问题，但所有问题都包含偶数，就像0^a 1^a，但现在我有3个值。我发现an example有关但我不能转换我的问题。

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 

我该如何转换abacaa？

Answer 1

我知道这已经有一段时间了，但只是为了防止有人在寻找类似的问题......为什么要重新这样做呢？

其基本思想是：一个下推自动机有一个堆栈。因此，请按照您的意愿阅读尽可能多的a，然后每次将额外的“a”推入堆栈。然后阅读b并转到下一个状态。

现在再次读取尽可能多的a，将所有a再次推入堆栈。然后阅读c并转到下一个状态。

现在，只要您正在查看堆栈顶部的'a'，就阅读a。当您查看堆栈底部符号时，转换到最终接受状态。

如果你有更多的a，没有转换，并且你的字符串不被接受（你没有阅读过，而且你没有去留，所以你“崩溃”了机器）。否则，如果您在以前的状态中用完了a，则永远不会使其进入最终状态，并且您的字符串不被接受。 只有当您刚刚阅读了与前两次一样多的a时，才会以接受状态结束，并且没有更多输入可供读取，并且字符串被接受。