问题
单项选择题
语言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-1=αn-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)。