“下推自动机”的设计识别语言：a^ib^2i
我正在学习自动考试和正式语言，我必须设计一个能够识别该语言的 PDA：
a ^ib ^2i 使得 i>= 1
我认为解决方案是：
从磁带读取的每个“a”我堆叠两个 X 然后，如果我在磁带上得到一个“b”并且顶部有一个 X堆栈，我弹出堆栈一个X，最后，如果我读空磁带，并且我有Zo（堆栈标记的底部），则该字符串被接受。我的问题是：我可以在一个计算步骤中堆叠两个连续的 X 吗？
I'm studying for my exam automata and formal languages, I have to design a PDA that recognizes the language:
a ^i b ^2i such that i>= 1
I thought the solution would be:
Each "a" read from the tape I stack two X Then, If I get a "b" on the tape and I have an X in the top of the stack, I pop of the stack one X, finally, if I read empty tape, and I have Zo (bottom of stack marker), the string is accepted. My question is: I can stack two consecutive X's in one computational step?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
您不需要在一步中推送两个 X，只需推送一个 X，然后转换到一种推送另一个 X 的状态，而不消耗磁带中的任何内容。请记住，转换函数是 sigma UNION {epsilon}，因此您可以在不消耗任何输入的情况下扰乱堆栈。
简短的回答：你想对堆栈做 N 件事吗？建立 N 个状态。只要确保提前知道 N 就可以了:)
you don't need to push two X's in one step, just push one X, and then transition to a state that pushes another X without consuming anything from the tape. Remember that the transition function is sigma UNION {epsilon}, so you can mess with the stack without consuming any input.
Short answer: you want to do N things to the stack? Make N states. Just be sure N is known in advance :)
这取决于您如何定义“下推自动机”，特别是您如何定义转换函数。您当然可以以允许一次推送整个字符串的方式定义 PDA。您需要检查您的课程文本或与您的教授一起查看课程中是否允许此类内容。
It depends on how you're defining "pushdown automaton", and specifically, how you're defining the transition function. You can certainly define PDAs in such a way as to allow pushing entire strings at a time. You need to check your course text or with your professor to see whether that kind of thing is going to be allowed in the course.