单选题 对于以下编号为①、②、③的正则式,正确的说法是______。
①(a*b*)*b ②(a|b)*b ③(b*|a*)*b
  • A.正则式①、②等价
  • B.正则式①、③等价
  • C.正则式②、③等价
  • D.正则式①、②,③等价
【正确答案】 C
【答案解析】[解析] 本题主要体现对闭包的理解。
正则闭包:A+=A12∪A3∪…∪An∪…(也就是所有幂的组合)。闭包:A*=A0∪A+(在正则闭包的基础上,加上A0={ε})。比如a*={a,aa,aaa,…,ε},而(ab)*={ab,abab,ababab,…,ε}。
正规式中的运算符“|”、“·”、“*”分别称为“或”、“连接”和“闭包”。在正规式的书写中,连接运算符“·”可省略。运算的优先级从高到低顺序排列为:“*”、“·”、“|”。
那么在本题中,(a*b*)*b所表示的含义就是以b结尾的且只包含a和b字符的任意字符串。
在正则式(a|b)*b中,闭包内的可以选a也可选b,而且a和b在最终字符串中的顺序没有确定,可以是任意的,因此该正则式所表示的含义也是以b结尾的且只包含a和b字符的任意字符串。
在正则式(b*|a*)*b中,括号包内的可以选a*也可选b*,然后对结果进行闭包,同样的道理,a和b在最终字符串中的顺序没有确定,可以是任意的,因此该正则式所表示的含义也是以b结尾的且只包含a和b字符的任意字符串。
综上所述,可知题目中给出的三个正则式都表示以b结尾的且只包含a和b字符的任意字符串,因此是等价的。