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

Question

Produce a PDA to recognise the following language : the language of strings containing more a's than b's

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

Answer 1

你的“a多于b”的问题可以通过PDA解决。

您所要做的就是:

• 当输入为 a 并且堆栈为空或顶部有 a 时，将 a 压入堆栈;如果 b 位于顶部，则弹出 b。

• 当输入为 b 并且堆栈为空或顶部有 b 时，将 b 压入堆栈;如果 a 位于顶部，则弹出 a。

• 最后，当字符串完成时，如果 a 位于堆栈顶部，则进入具有 null 输入的最终状态。否则，a 的数量不会多于 b 的数量。