在仅由字符a、b构成的所有字符串中，其中以b结尾的字符串集合可用正规式表示为( )。

第21题

知识点：正规表达式和正规集

关键词：字符串章/节：计算机软件基础知识

A. (b|ab)*b

B. (ab*)*b

C. a*b*b

D. (a|b)*b

正规表达式和正规集

对于字母表∑，其上的正规式及其表示的正规集可以递归定义如下：

（1）ε是一个正规式，它表示集合L（ε）=｛ε｝。

（2）若a是∑上的字符，则a是一个正规式，它所表示的正规集为｛a｝。

（3）若正规式r和s分别表示正规集L（r）和L（s），则：

①r\s是正规式，表示集合L（r）∪L（s）。

②r·s是正规式，表示集合L（r）L（s）。

③r^*是正规式，表示集合（L（r））^*。

④（r）是正规式，表示集合L（r）。

仅由有限次地使用上述三个步骤定义的表达式才是∑上的正规式，其中运算符“｜”“.”“*”分别称为“或”“连接”“闭包”。在正规式的书写中，连接运算符“.”可省略。运算符的优先级从高到低顺序排列为“*”“.”“｜”。

设∑=｛a，b｝，下表列出了∑上的一些正规式和相应的正规集。

正规式与正规集示例

若两个正规式表示的正规集相同，则认为二者等价。两个等价的正规式U和V记为U=V。例如，b（ab）^*=（ba）^*b，（a｜b）^*=（a^*b^*）^*。设U、V和W均为正规式，正规式的代数性质如下表所示。

正规式的代数性质

题号导航 2017年上半年数据库系统工程师上午试卷综合知识