大门|大门-CS-2009 |问题15

以下哪一项是错误的？

（A） 每种常规语言都有唯一的最小DFA （B） 每个NFA都可以转换成同等的PDA。 （C） 每种上下文无关语言的补码都是递归的。 （D） 每个非确定性PDA都可以转换为等效的确定性PDA。 答复: （D） 说明： 确定性PDA的功率与非确定性PDA的功率不同。确定性PDA不能处理有歧义的语言或语法，但NDPDA可以处理有歧义的语言和任何上下文无关的语法。因此，每一个非确定性PDA都不能转化为一个等价的确定性PDA。 这个问题的小测验