【正确答案】
D
【答案解析】[解析] 用正规式定义一些简单的语言,但是很多复杂一些的语言不能用正规式表达。例如,正规式不能用于描述配对或嵌套的结构,具体的例子有由配对括号构成的串的集合不能用正规式描述,语句的嵌套结构也不能用正规式描述;还有,重复串也不能用正规式表示,如集合{wcw|w是a和b的串}不能用正规式描述。
正规式只能表示给定结构的固定次数的重复或没有指定次数的重复。在本题中,指定了重复的次数m,但m又不是固定的,所以也不能使用正规式表示。
有限状态自动机识别的语言是正规语言。对于每个非确定的有限自动机,都有一个与其等价的正规式。因此,题目中的集合既然不能使用正规式表达,也就不能用非确定的有限自动机识别。
上下文无关文法的描述功能比正规式更强,正规式可以描述的每种结构都可以用上下语言无关文法来描述,但反之不然。上下文无关文法能表示次数不固定的重复。因此本题的答案选D。