我正在为我的考试自动机和正式语言学习，我必须设计一个识别语言的 PDA：
一个 ^ib ^2i 使得 i>= 1
我认为解决方案是：
从磁带上读取的每个“a”我堆叠两个 X 然后，如果我在磁带上得到一个“b”并且我在堆栈顶部有一个 X，我从堆栈中弹出一个 X，最后，如果我读到空磁带，我有 Zo（堆栈标记的底部），字符串被接受。我的问题是：我可以在一个计算步骤中堆叠两个连续的 X 吗？
2 回答
2
您不需要一步推动两个 X，只需推动一个 X，然后转换到推动另一个 X 而不消耗磁带中的任何内容的状态。请记住，转换函数是 sigma UNION {epsilon}，因此您可以在不消耗任何输入的情况下弄乱堆栈。
简短的回答：你想对堆栈做 N 件事吗？做 N 个状态。只需确保提前知道 N :)
于 2012-02-09T15:48:04.097 回答
0
我可以在一个计算步骤中堆叠两个连续的 X 吗？
这取决于您如何定义“下推自动机”，特别是您如何定义转换函数。您当然可以将 PDA 定义为允许一次推送整个字符串。您需要检查您的课程文本或与您的教授一起查看课程中是否允许这种事情。
于 2012-02-09T16:15:34.510 回答