形式语言第4章正则表达式

《形式语言第4章正则表达式》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2021/9/171第4章正则表达式正则文法擅长语言的产生，有穷状态自动机擅长语言的识别。本章讨论正则语言的正则表达式描述。它在对正则语言的表达上具有特殊的优势，为正则语言的计算机处理提供了方便条件。简洁、更接近语言的集合表示和语言的计算机表示等。2021/9/172第4章正则表达式主要内容典型RE的构造。与RE等价FA的构造方法。与DFA等价的RE的构造。重点RE的概念。RE与DFA的等价性。难点：RE与DFA的等价性证明。2021/9/1734.１启示产生语言{anbmck

2、n，m，k≥1}∪{aicnbxam

3、i≥0,n≥1,m≥2,x为d和e组成的串}的正则文法为A

4、aA

5、aB

6、cEBbB

7、bCCcC

8、cEcE

9、bFFdF

10、eF

11、aHHaH

12、a2021/9/1744.１启示接受此语言的NFAM2021/9/1754.１启示计算集合set(q)set(A)={an

13、n≥0}={a}*set(B)=set(A){a}{bn

14、n≥0}={anabm

15、m，n≥0}={a}*{a}{b}*={a}+{b}*set(C)=set(B){b}{c}*={a}*{a}{b}*{b}{c}*={a}+{b}+{c}*set(D)=set(C){c}={a}+{b}+{c}*{c}={a}+{b}+{c}+2021/9/1764.１启示set(

16、E)=set(A){c}{c}*={a}*{c}{c}*={a}*{c}+set(F)=set(E){b}{d，e}*={a}*{c}+{b}{d，e}*set(H)=set(F){a}{a}*={a}*{c}+{b}{d，e}*{a}{a}*={a}*{c}+{b}{d，e}*{a}+set(I)=set(H){a}={a}*{c}+{b}{d，e}*{a}+{a}L(M)=set(D)∪set(H)={a}+{b}+{c}+∪{a}*{c}+{b}{d，e}*{a}+{a}2021/9/1774.１启示根据集合运算的定义，{d，e}={d}∪{e}。从而，{d，e}*=

17、({d}∪{e})*。这样可以将L(M)写成如下形式：L(M)={a}+{b}+{c}+∪{a}*{c}+{b}({d}∪{e})*{a}+{a}记作：a+b+c++a*c+b(d+e)*a+a=aa*bb*cc*+a*cc*b(d+e)*aaa*2021/9/1784.2RE的形式定义正则表达式(regularexpression，RE)⑴Φ是∑上的RE，它表示语言Φ；⑵ε是∑上的RE，它表示语言{ε}；⑶对于a∈∑，a是∑上的RE，它表示语言{a}；2021/9/1794.2RE的形式定义⑷如果r和s分别是∑上表示语言R和S的RE，则：r与s的“和”(r+s)是∑上的

18、RE，(r+s)表达的语言为R∪S；r与s的“乘积”(rs)是∑上的RE，(rs)表达的语言为RS；r的克林闭包(r*)是∑上的RE，(r*)表达的语言为R*。⑸只有满足⑴、⑵、⑶、⑷的才是∑上的RE。2021/9/17104.2RE的形式定义例4-1设∑={0，1}⑴0，表示语言{0}；⑵1，表示语言{1}；⑶(0+1)，表示语言{0，1}；⑷(01)，表示语言{01}；⑸((0+1)*)，表示语言{0，1}*；⑹((00)((00)*))，表示语言{00}{00}*；2021/9/17114.2RE的形式定义⑺((((0+1)*)(0+1))((0+1)*)),表示语言

19、{0，1}+；⑻((((0+1)*)000)((0+1)*))，表示{0，1}上的至少含有3个连续0的串组成的语言；⑼((((0+1)*)0)1)，表示所有以01结尾的0、1字符串组成的语言；⑽(1(((0+1)*)0))，表示所有以1开头，并且以0结尾的0、1字符串组成的语言。2021/9/17124.2RE的形式定义约定⑴r的正闭包r+表示r与(r*)的乘积以及(r*)与r的乘积：r+=(r(r*))=((r*)r)⑵闭包运算的优先级最高，乘运算的优先级次之，加运算“+”的优先级最低。所以，在意义明确时，可以省略其中某些括号。((((0+1)*)000)((0+1)*)

20、)=(0+1)*000(0+1)*2021/9/17134.2RE的形式定义((((0+1)*)(0+1))((0+1)*))=(0+1)*(0+1)(0+1)*⑶在意义明确时，REr表示的语言记为L(r)，也可以直接地记为r。⑷加、乘、闭包运算均执行左结合规则。2021/9/17144.2RE的形式定义相等(equivalence)r、s是字母表∑上的一个RE，如果L(r)=L(s)，则称r与s相等，记作r=s。相等也称为等价。几个基本结论⑴结合律：(rs)t=r(st)(r+s)+t=r+(s+t)⑵分配律：r