PDA接受包含比b更多的字符串的语言

Question

制作PDA以识别以下语言:包含比b更多的字符串的语言

我几天来一直在努力解决这个问题,我似乎已经完成了一个完整的心理障碍.是否有人能够为我如何解决这个问题提供一些指导或指导？

Answer 1

您可以通过PDA解决"更多不是b"的问题.

你所要做的就是:

• 当输入是a并且堆栈为空或a顶部有一个时,请按下a堆栈; pop b,如果b是顶部.

• 当输入是b并且堆栈为空或b顶部有一个时,请按下b堆栈; pop a,如果a在顶部.

• 最后,当字符串完成时,如果a位于堆栈顶部,则转到具有空输入的最终状态.否则你没有a比这更多b的了.

Answer 2

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

这个想法相对简单，因为a您将其压入堆栈（在循环中），因为b您切换到单独的循环以a从堆栈中弹出。如果堆栈为空，您将因失败而放弃。如果在第一个循环中您得到除a或之外的任何内容b，或者在第二个循环中您得到除 之外的任何内容b，则您会因失败而放弃。

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

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