automata - PDA 接受包含 a 多于 b 的字符串语言

Question

制作 PDA 以识别以下语言：a 多于 b 的字符串语言

我已经为这个问题苦苦挣扎了好几天了，我似乎已经完全陷入了精神障碍。任何人都可以为我如何解决这个问题提供一些指导或指导吗？

Answer 1

PDA 可以解决您“a 多于 b”的问题。

你所要做的就是：

• 当输入为a且堆栈为空或a顶部有一个时，推入a堆栈；pop b，如果b是顶部。

• 当输入为b且堆栈为空或b顶部有一个时，推入b堆栈；pop a，如果a在顶部。

• a最后，当字符串完成时，如果在堆栈顶部，则使用 null 输入进入最终状态。否则你没有a比's 更多的b's 。

Answer 2

关于as和bs数量的问题，我想出了一个更通用的解决方案，见下图：

其中 a > b 比 bs 意味着更多，a < b , a = b 也是如此。

Z 表示栈底，A/B 为栈符号。

我很兴奋，因为这个 PDA 将 3 个不同的状态分开。在您的问题中，您可以将 a > b 状态设置为最终状态，并让 a = b 成为开始状态。

如果您想更进一步，您可以使用此 PDA 轻松生成 a >= b、a - b >= 1、2 <= a - b <= 3 等的 PDA，这很有趣。

Answer 3

我假设您的意思是形式的字符串a^nb^m，其中n> m。

这个想法相对简单，因为a你将它压入堆栈（在一个循环中），因为b你切换到一个单独的循环以a从堆栈中弹出。如果堆栈是空的，你放弃失败。如果在第一个循环中你得到除aor以外的任何东西b，或者在第二个循环中你得到除 之外的任何东西b，你就放弃了 FAIL。

最后，您尝试弹出另一个a，如果堆栈为空，您将放弃 FAIL（即，堆栈上的 ' 至少与b'一样多a，可能更多）。如果没有，成功。

编辑：作为旁注，我不相信这是解决这个问题的正确网站，可能对程序员更好。不确定，所以不投票关闭。

Answer 4

PDA 接受的 a 多于 b

Answer 5

交易基本信息如下图所示。

这是完整的交易。

其中є等于NULL。 $ 符号在字符串的开头被压入堆栈并在末尾弹出以确定字符串已被完全读取并现在结束。qo 是开始状态，q5 是最终状态

它是非确定性下推自动机（NPDA）。因此，由于 NPDA，拒绝字符串的交易不会显示在其中。