如何创建接受语言的下推自动机？

Question

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

Answer 1

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

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