对于以下编号为①、②、③的正规式,说法正确的是(28)。①(aa*|ab)*b②(a|b*|aa)*b③(a|b)*bA.正规式①和③等

Question

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

A．正规式①和③等价

B．正规式①和②等价

C．正规式②和③等价

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

Answer 1

正确答案：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。