∑={a,b}上的正规表达式(a|b)*(aa|bb)(a|b)*描述的正规集是(27)。A.由a和b组成的所有串B.由a和b组

Question

∑＝{a,b}上的正规表达式(a|b)*(aa|bb)(a|b)*描述的正规集是(27)。

A．由a和b组成的所有串

B．由a和b组成的串，且其中含有子串aa

C．由a和b组成的串，且其中含有子串aa和子串bb

D．由a和b组成的串，且其中或含有子串aa，或含有子串bb

Answer 1

正确答案：D
解析：用正规表达式(简称正规式)可以描述一个程序语言的单词集合，它表示的集合称为正规集。对于字母表∑而言，正规式和它所表示的正规集递归定义如下所述。(1)ε和是正规式，它们所表示的正规集分别为{ε}和；(2)a∈∑，a是正规式，它所表示的正规集为{a}；(3)设r和s是∑上的正规式，它们所表示的正规集分别为L(r)和L(s)，那么(r|s)、(rs)(连接)和(r)*也是正规式，它们所表示的正规集分别为L(r)∪L(s)、L(r)L(s)和(L(r))*。(4)仅由有限次使用以上3个运算构造出的表达式才是正规式。正规式中运算符的优先级从高到低依次是：*、连接和|。算术表达式表示计算规则，已知一个算术表达式，人们按照它所表示的计算规则能计算出一个算术值；正规表达式表示集合的计算规则，已知一个正规表达式，按照它所表示的计算规则，通过计算能得到一个正规集合。仿照计算算术表达式计算正规表达式(a|b)*(aa|bb)(a|b)*如下：正规式a|b描述的是集合(a}∪(b}＝{a,b)，(a|b)*描述的集合是{a,b}*，{a,b}*是由a和b组成的所有串的集合。正规式aa描述的集合是{aa}，正规式(aa|bb)描述的集合是{aa}∪{bb}＝{aa,bb}。正规式(a|b)*(aa，bb)(a|b)*描述的集合是把{a,b}*、{aa,bb}、{a,b}*3者连接起来。