问题 单项选择题

语言L=0m1n|m≥1,n≥1)的正规表达式是()。

A.0*1*

B.00*1*

C.0*11*

D.00*11*

答案

参考答案:D

解析:

先考虑字和字集的运算。设α,β是∑上的字,则:

连接:字α,β的连接αβ是把字β写在字α之后。显然,εα=αε=α。

方幂:把连接看作字的乘运算,字α自身连接n次得到的字称为α的n次方幂,记为αn,那么α0=ε,α1=α,αn=ααn-1n-1α(n>0)。

以下是字集运算,设L,M是∑上的字集,则

并:LUM={w|w∈L或w∈M}。

积(连接):LM={w1w2|w1∈L且w2∈M}。

幂:L0={ε},Ln=LLn-1=Ln-1L(n>0)。

闭包:L*=L0∪L1∪L2∪L3∪…。

0*表示集合({0})*={ε,0,00,000,…,0m,…}={0m|m≥0}。

0*1*表示集合({0))*({1))*={0m1n|m≥0,n≥0}。

00*表示集合{0}({0))*={0}{ε,0,00,000,…,0m,…)={0,00,000,…,0m,…}={0m|m≥1}。

00*11*={0m1n|m≥1,n≥1)。

单项选择题
单项选择题