问题 单项选择题

对于以下编号为①、②、③的正规式,说法正确的是()。

①(aa*|ab)*b

②(a|b*|aa)*b

③(a|b)*b

A.正规式①和③等价

B.正规式①和②等价

C.正规式②和③等价

D.正规式①、②和③互不等价

答案

参考答案:C

解析:

[要点解析] 根据正规式r和s的意义,两个正规式等价说明r和s代表的字符串集合相同,因此可用证明集合相等的方法判断。另外,也可构造出与每个正规式对应的自动机进行说明。但是这两个方法实施起来都很烦琐,一种比较简便的方法是,根据正规式的含义及其代数性质进行判断。 由于题目中给出的正规式①、②和③的共同之处是以字符b结尾,因此只需考虑正规式“(aa*|ab)*”、 “((a|b)*|aa)*”和“(a|b)*”之间的等价关系。从直观的角度理解,正规式“(aa*|ab)*”表示的是包含空串 ε及a开头的且每个b之后必然出现a的字符串的集合;而正规式“(a|b)*”表示包含空串ε在内的所有a 和b构成的字符串集合,并不限制b的出现方式;正规式“((a|b)*|aa)*”表示的字符串也不具有必须以a 开头的特点。因此,正规式①与②和正规式①与③的等价关系即可排除,即先排除选项A和B。 由于“(a|b)*”已经包括了含有“aa”子串的所有a和b字符串,因此,对于正规式“((a|b)*|aa)*”中 的“aa”可省略,即正规式“((a|b)*|aa)*”与“(a|b)*”是等价的,故正确答案是选项C。

单项选择题
判断题