对于以下编号为①、②、③的正规式,正确的说法是______。
①(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)*,很明显后者中的aa是画蛇添足的部分,因为(a|b)*已经包含了含有aa字串的所有a、b字符串。因此,(a|b)*b和((a|b)*|aa)*b是等价的。
本题也可以从另一个角度来解答,将这些正规式进行化简后再进行比较,①(aa*|ab)*b产生的字符串为a*b或ab*b;②(a|b)*b产生的字符串为a*b或b*b;③((a|b)*|aa)*b产生的字符串为a*b或b*b。