大三下课程编译原理

Ch2Ch2形式语言自动机理论基 2.3正规式与自动21Ch2Ch2形式语言自动机理论基 2.3正规式与自动22CCh22.12.1.5，Ch2形式语言自动机理论基 2.3正规式与自动 2.3.1有限自动机与正则文Ch2形式语言自动机理论基 2.3正规式与自动 2.3.1有限自动机与正则文Ch2Ch2形式语言自动机理论基 2.3正规式与自动26Ch2Ch2形式语言自动机理论基 2.3正规式与自动 2.3.1正规式与正规

若r,s对应的正规集分别为R和S则7 2.3正规式与自动 2.3.1正规式与正规1.正规式与相应的正规集是等价的，正规集给出了2.3.4.运算符•CCh2形式语言自动机理论基 2.3正规式与自动 2.3.1正规式与正规例2.32令=010，1，ε和Ф都是0|0•1•(0|1)0*(

{0，1{01{10{ε,0,00,000,…{ε,1,11,111,…{0,00,000,…,1,10,100,1000,{001,1019CCh2形式语言自动机理论基 2.3正规式与自动 2.3.1正规式与正规称为正则语言，用L(r)表示，即R=L(r)。L(r)中的元素为字符串，称为L(r)的句子。若两个正规式r和sL(r)=L(s)，则称r,sr=s。例2.33=V=(A|B)(A|B|0|V=(0|1)(0|Ch2形式语言自动机理论基 2.3正规式与自动 2.3.1正规式与正规例2.34：令Ch2形式语言自动机理论基 2.3正规式与自动 2.3.1正规式与正规r=(+|-|ε r=(+|- (dd*.d*|d*.dd*)(ε|(E(+|-|ε)dd*11CCh2形式语言自动机理论基 2.3正规式与自动 2.3.1正规式与正规①⑥⑾

② ⑧⑿ ⒀

⑤ ⑩ < BEGIN|END|IF|THEN| <字母>(<字母>|<数字 >|>=|<|<=|=|<12Ch2形式语言自动机理论基Ch2形式语言自动机理论基 2.3正规式与自动 2.3.1正规式与正规s|t=t||s|(t|r)=(s|t)||(st)r=s(ts(t|r)=st|s(t|r)s=ts|rεs=s(sε=s*=(sa**=aCh2Ch2形式语言自动机理论基 2.3正规式与自动214上的FAM，使得V=L(M)若有∑上的FAM，构造正规式V使L(M∑上任何正规式V，构造相应的FAML(ML(V)若有∑上的FAM，构造正规式V，使L(M)=L(V)；Z有NFAM1b1bqεS0ba2εqZ3aε417ABAB

AABACAC

AABACBAR1AR1R2*BB

18qS0bb1εa2εεqZ3a422εε1ε42εε1ε40 00 0000000有FAM0bccb1ba223

0

0

c 0bbc1aa0b10b10b1a|ca|c(a|)c0b1qqs0

0260

qqs272： 1)1)若所有弧上标记是ε或∑上的字符ai, RR⑵C⑶CNFAM’有V1251263151265126qZ56a5134a26 01213221435646435 012

012

21032103 01ab2ab01201213132233 3738cch2

39ch2ch240 SaA| A→a|要求：本题构造步骤是按照词则先构造识411.1.一部文法G的文法符号不是VN就是VT