为以下语言创建下推自动机
Create a pushdown automata for the following language
所以我在做书中的练习题时发现了这个问题。
在 sigma(a,b,c).
上构造一个接受语言 L 的 npda
L={w:a的个数=b的个数+1}
所以我将其解释为它接受所有比字母 b 多一个 a 的字符串。我相信所有的州都应该有一个有过渡的循环（c，landa，landa），因为我们并不真正关心 c。在此之后我真的很困惑，因为 a 和 b 的位置是任意的，所以要涵盖的情况太多了。解决这个问题的方法是什么？谢谢！！
PDA 可以使用堆栈来记住任意数量的信息。这使得 PDA 比有限自动机更强大。确定 PDA 的关键是弄清楚堆栈将如何使用，然后围绕它构建 PDA。
我们如何使用堆栈来确保 a 的数量等于 b 的数量加一？嗯，堆栈可以很容易地跟踪已看到的符号的 运行 平衡。例如，如果我们看到四个 a 和两个 b，我们的堆栈可能通过包含 aaZ 来表示这一事实，其中 Z 是 "bottom of stack"象征。当然，我们可能会使用其他方法和其他表示法，但对于这个 class 问题，这是一个特别巧妙的方法。完整解释表示：
- 堆栈最初是
Z，只是堆栈符号的底部。
- 如果我们看到
a 并且栈顶是 a 或 Z，我们添加另一个 a.
- 如果我们看到一个
a 并且堆栈的顶部是 b，我们将删除一个 b。
- 如果我们看到一个
b 并且堆栈的顶部是 b 或 Z，我们添加另一个 b.
- 如果我们看到
b 并且栈顶是 a，我们删除一个 a。
- 如果我们看到
c，请不要管堆栈。
如果我们对所有输入一遍又一遍地这样做，那么堆栈的内容将等于 x^m，其中 x 是 a 和 b出现的次数较多，m是各符号个数之差的绝对值。
要接受您的语言，您必须简单地识别输入已用完并且堆栈包含等于 aZ 的情况。这可以通过添加一些状态和 lambda/epsilon 转换来清除堆栈来完成 and/or 进入接受状态。
感谢 Peter Leupold 指出原始答案的其余部分语法错误。我试图修复它，但不喜欢答案持续了多长时间，所以我忽略了它。我将简单地补充一点，另一种可能性是为一种语言生成一个 CFG，并使用一种算法为它派生出一个 PDA。这样的话，对我来说，直接给PDA就省事多了。
所以我在做书中的练习题时发现了这个问题。 在 sigma(a,b,c).
上构造一个接受语言 L 的 npdaL={w:a的个数=b的个数+1}
所以我将其解释为它接受所有比字母 b 多一个 a 的字符串。我相信所有的州都应该有一个有过渡的循环（c，landa，landa），因为我们并不真正关心 c。在此之后我真的很困惑，因为 a 和 b 的位置是任意的，所以要涵盖的情况太多了。解决这个问题的方法是什么？谢谢！！
PDA 可以使用堆栈来记住任意数量的信息。这使得 PDA 比有限自动机更强大。确定 PDA 的关键是弄清楚堆栈将如何使用，然后围绕它构建 PDA。
我们如何使用堆栈来确保 a 的数量等于 b 的数量加一？嗯，堆栈可以很容易地跟踪已看到的符号的 运行 平衡。例如，如果我们看到四个 a 和两个 b，我们的堆栈可能通过包含 aaZ 来表示这一事实，其中 Z 是 "bottom of stack"象征。当然，我们可能会使用其他方法和其他表示法，但对于这个 class 问题，这是一个特别巧妙的方法。完整解释表示：
- 堆栈最初是
Z，只是堆栈符号的底部。 - 如果我们看到
a并且栈顶是a或Z，我们添加另一个a. - 如果我们看到一个
a并且堆栈的顶部是b，我们将删除一个b。 - 如果我们看到一个
b并且堆栈的顶部是b或Z，我们添加另一个b. - 如果我们看到
b并且栈顶是a，我们删除一个a。 - 如果我们看到
c，请不要管堆栈。
如果我们对所有输入一遍又一遍地这样做，那么堆栈的内容将等于 x^m，其中 x 是 a 和 b出现的次数较多，m是各符号个数之差的绝对值。
要接受您的语言，您必须简单地识别输入已用完并且堆栈包含等于 aZ 的情况。这可以通过添加一些状态和 lambda/epsilon 转换来清除堆栈来完成 and/or 进入接受状态。
感谢 Peter Leupold 指出原始答案的其余部分语法错误。我试图修复它，但不喜欢答案持续了多长时间，所以我忽略了它。我将简单地补充一点，另一种可能性是为一种语言生成一个 CFG，并使用一种算法为它派生出一个 PDA。这样的话，对我来说，直接给PDA就省事多了。