computer-science - 如何创建一个接受语言的下推自动机？

Question

有人可以向我解释如何为这种语言创建下推自动机。如果您能解释一下，我不明白该语言的集合符号也很好。谢谢

Answer 1

符号的意思是：由所有以 n 个字母 a 开头，后面跟着 m 个字母 b 的单词组成的语言；此外，数字 n 和 m 不能相等。

用 PDA 接受这一点的明显方法是：从一开始，你每读到一个 a，你就在堆栈上放一个；当您开始看到 b 时，对于您读取的每个 b，您都会从堆栈中删除一个 a。如果最后一个 b 删除了最后一个堆栈符号，那么 n=m 并且 PDA 应该拒绝；否则，如果单词来自 a b它应该接受。