GATE | GATE IT 2006 |问题31

以下哪种语言被非确定性下推自动机（PDA）接受，而不是被确定性PDA接受？ （A） {a ^N B ^N C ^N ∣ N≥0} （B） {a ^L B ^M C ^N ∣ L≠m还是m≠n} （C） {a ^N B ^N ∣ N≥0} （D） {a ^M B ^N ∣ m、 n≥0} 答复: （B） 说明：

1.L={ANNBNCN | n>=0}这不是CFL，因为没有PDA可以派生这种语言。 用泵引理也可以证明这一点，从直觉上也可以看出。[不正确]

2.L={a L b m c n | L！=m或m！=n}是两个CFL L1={a L b m c n | L！=m}和L2的并集= {a l b m c n | m！=n}都有DPDA。所以我确定是CFL，所以它会有DFA， 虽然不一定是确定性的。L={ANBNBNCNN}和DPDA在 互补性——因此，如果L是DPDA，那么它的互补性也应该是DPDA， 但事实并非如此。因此，L被NPDA接受。[正确]

3.L={a n b n |n≥ 0}可以从确定性PDA派生，如果当前字母表是 如果是b，则弹出。如果堆栈在字符串末尾为空，则接受，否则拒绝。[不正确]

4.L={a n b m | n，m≥ 0}是形式为a的正则语言∗ B∗ , 因此它有一个DPDA。[不正确]

参考：

https://cs.wmich.edu/elise/courses/cs6800/DCFL.pptx

这个解决方案是由 维内特·珀斯瓦尼 . 这个问题的小测验