感谢NPDA接受语言L={an bn cm|m，n>=1}

先决条件—— 下推自动机 , 下推自动机最终状态验收

问题 –设计一个非确定性PDA，用于接受语言L={ |m，n>=1}，即。，

L = { abc, abcc, abccc,  aabbc, aaabbbcc, aaaabbbbccccc, ...... }

在每个字符串中，a的数量等于b的数量。c的数量与a和b的数量无关。这个问题与NPDA接受语言L={ |n>=1}。唯一的区别是我们在这里添加 .

解释—— 在这里，我们需要保持a，b和c的顺序。也就是说，所有的a都先来，然后所有的b和c都来。因此，我们需要一个堆栈和状态图。a和b的计数由堆栈维护。我们将采用两种堆叠字母：

 = { a, z }

哪里， =所有堆栈字母表的集合 z=堆栈开始符号

PDA构建中使用的方法- 因为我们想要设计一个NPDA，所以每次“a”出现在“b”之前。当“a”出现时，将其推入堆栈，如果“a”再次出现，则也将其推入堆栈。之后，当“b”出现时，每次从堆栈中弹出一个“a”。那么对于c，我们什么也不做。 因此，在最后，如果堆栈变为空，那么我们可以说字符串被PDA接受。

堆栈转换函数-

(q0, a, z)  (q0, az)
(q0, a, a)  (q0, aa)
(q0, b, a)  (q1,  )
(q1, b, a)  (q1,  )
(q1, c, z)  (qf, z )
(qf, c, z)  (qf, z )
        

式中，q0=初始状态 qf=最终状态 =表示pop操作

这是我们接受语言L={ |m，n>=1}