GATE | GATE CS 2013 |问题41

以下哪项是不可判定的？

（A） 3只 （B） 只有3和4 （C） 仅限1、2和3 （D） 只有2和3 答复: （D） 说明：

• 首先是对CFG的空虚；无论CFG是否为空，这个问题都是可以确定的。
• 二是一切为了CFG；CFG是否会生成所有可能的字符串（CFG的完整性），这个问题是无法确定的。
• 第三是REC的规律性；由TM生成的语言是否是正则的是不可判定的。
• 第四是正则表达式的等价性；DFA和NFA生成的语言是否相同是可以确定的。

第二个和第三个是不可判定的。因此，选项（D）是正确的。

这个问题的小测验