下推自动机 (a^xba^yca^x+y )
我的朋友问我一个关于下推自动机的问题。马尼拉麻。我正在研究一些类似的问题，但所有问题都包含偶数，就像 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
我怎样才能转换蕉麻？
My friend asked me a question about pushdown automaton. abacaa. I'm looking at some similar problems but all problems contain even numbers just like 0^a 1^a but now I have 3 values. I've found an example about that but i can't convert my question to this.
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
How can i convert abacaa ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我知道这已经有一段时间了，但以防万一有人正在寻找类似的问题......为什么要重复这个？
基本思想是这样的：下推自动机有一个堆栈。因此，读入任意数量的 a，每次将一个额外的“a”推入堆栈。然后读取b并进入下一个状态。
现在再次读取任意多个 a，并将所有 a 再次压入堆栈。然后读取ac并进入下一个状态。
现在，只要您正在查看堆栈顶部的“a”，就可以读取a。当您查看堆栈底部符号时，转换到最终接受状态。
如果你有更多的 a，则没有转换，并且你的字符串不被接受（你还没有完成阅读，并且你无处可去，所以你“崩溃”了机器）。否则，如果您在前一个状态中用完了 a，则您永远不会到达最终状态，并且您的字符串不会被接受。 只有当您读取了与前两次一样多的 a 时，您才会最终处于接受状态，不再需要读取任何输入，并且字符串会被接受。
I know this has been here a while, but just in case anybody is searching for similar questions... why rehash this?
The basic idea is this: a pushdown automaton has a stack. So, read in as many a's as you want, pushing an extra "a" to the stack each time. Then read b and go to the next state.
Now read as many a's as you want again, pushing all a's onto the stack again. Then read a c and go to the next state.
Now, read a's as long as you are looking at an 'a' on the top of the stack. When you are looking at the bottom-of-the-stack symbol, transition to a final accepting state.
If you have more a's, there are no transitions and your string is not accepted (you're not done reading, and you have nowhere left to go, so you "crash" the machine). Otherwise, if you ran out of a's in the previous state, you never make it to the final state and your string is not accepted. Only if you just read as many a's as you did the first two times do you end up in the accepting state with no more input to read, and the string is accepted.