2. 计算机
  3. 集合L={ambm｜m≥0)(12)。

集合L={ambm｜m≥0)(12)。

admin2015-06-03  2
问题 集合L={ambm｜m≥0)(12)。
选项 A、可用正规式“a*b*”表示
B、不能用正规式表示，但可用非确定的有限自动机识别
C、可用正规式“ambm”表示
D、不能用正规式表示，但可用上下文无关文法表示
答案D
解析 用正规式定义一些简单的语言，但是很多复杂一些的语言不能用正规式表达。例如，正规式不能用于描述配对或嵌套的结构，具体的例子有由配对括号构成的串的集合不能用正规式描述，语句的嵌套结构也不能用正规式描述；还有，重复串也不能用正规式表示，如集合{WCW｜W是a和b的串)不能用正规式描述。
    正规式只能表示给定结构的固定次数的重复或没有指定次数的重复。在本题中，指定了重复的次数m，但m又不是固定的，所以也不能使用正规式表示。
    有限状态自动机识别的语言是正规语言。对于每个非确定的有限自动机，都有一个与其等价的正规式。因此，题目中的集合既然不能使用正规式表达，也就不能用非确定的有限自动机识别。
    上下文无关文法的描述功能比正规式更强，正规式可以描述的每种结构都可以用上下语言无关文法来描述，但反之不然。上下文无关文法能表示次数不固定的重复。因此本题的答案选D。
转载请注明原文地址:https://kaotiyun.com/show/JCRZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

软件设计师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)