2. 计算机
  3. 对于以下编号为①、②、③的正规式，正确的说法是(30)。 ①(aa*|ab)*b　　　　 ②(a|b)*b　　　　 ③((a|b)*|aa)*b

对于以下编号为①、②、③的正规式，正确的说法是(30)。 ①(aa*|ab)*b　　　　 ②(a|b)*b　　　　 ③((a|b)*|aa)*b

admin2019-04-22  41
问题 对于以下编号为①、②、③的正规式，正确的说法是(30)。
①(aa*|ab)*b　　　　
②(a|b)*b　　　　
③((a|b)*|aa)*b
选项 A、正规式①、②等价
B、正规式①、③等价
C、正规式②、③等价
D、正规式①、②、③互不等价
答案C
解析 根据正规式r和s的意义，两个正规式等价说明r和s代表的字符串集合相同，因此可用证明集合相等的方法判断。另外，也可构造出与每个正规式对应的自动机进行说明。但是这两个方法实施起来都很繁琐，因此可根据正规式的含义及其代数性质进行判断。由于题目中给出的正规式①、②和③的共同之处是以字符b结尾，所以只需考虑(aa*|ab)*、(a|b)*和((a|b)*|aa)*之间的等价关系。从直观的角度理解，正规式(aa*|ab)*表示的是包含空串ε以及a开头的且每个b之后必然出现a的字符串的集合，而(a|b)*表示包含空串ε在内的所有a、b构成的字符串集合，并不限制b的出现方式，正规式((a|b)*|aa)*表示的字符串也不具有必须以a开头的特点，因此，正规式①与②、③的等价关系即可排除。至于(a|b)*和((a|b)*|aa)*，很明显正规式((a|b)*|aa)*中的“aa”是画蛇添足的部分，因为(a|b)*已经包括了含有“aa”子串的所有a、b字符串，因此(a|b)*b和((a|b)*|aa)*b是等价的。
转载请注明原文地址:https://kaotiyun.com/show/IYRZ777K
本试题收录于： 软件设计师上午基础知识考试题库软考中级分类
0

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

软考中级

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