形式语言与自动机3教学讲解教案.pdf

《形式语言与自动机3教学讲解教案.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、FL&A第三讲正规表达式与正规语言FL&A正规语言的不同表达形式NFADFA非确定有限自动机确定有限自动机正规语言regulargrammar正规文法（regularlanguages）ε-NFA带ε转移的非确regularexpressions定有限自动机正规表达式FL&A正规表达式与正规语言正规表达式正规语言正规表达式的代数性质FL&A正规表达式用代数的方法表示正规语言语义正规语言（RegularLanguages，RL）作用于正规语言上的三种代数运算:联合（union）LM=wwLwM

2、连接（concatenation）L·M=wwwLwM1212（星）闭包（closure）L*=Lii0语法基本正规表达式3个运算符vs.上述3个运算对应不同应用形式会扩展一些助记运算符如LEX中的正规表达式FL&A正规表达式语法设为字母表。上的正规表达式集合R递归定义如下:基础.1.,R.2.Ifa，thenaR.3.任一变量LR.归纳.1.IfERandFR，thenE+FR.2.IfERandFR，thenEFR.3.IfER，thenE*R.4.I

3、fER，then(E)R.FL&A正规表达式语义设R为上的正规表达式集合。每个ER的语言L(E)递归定义如下：基础.1.L()={}andL()=.2.Ifa，thenL(a)={a}.归纳.1.IfERandFR，thenL(E+F)=L(E)L(F).2.IfERandFR，thenL(EF)=L(E)L(F).3.IfER，thenL(E*)=(L(E))*.4.IfER，thenL((E))=L(E).FL&A正规表达式正规表达式算符优先级算符优先级（precedence

4、）依次为•连接FL&A正规表达式正规表达式的几个派生运算符L+=LL*=L*LL?=+LLn=LLn-1(n>0)L0=FL&A正规表达式正规表达式举例设计表示如下语言的正规表达式：该语言中的每个字符串由交替的0和1构成(01)*+(10)*+0(10)*+1(01)*(+1)(01)*(+0)(+0)(10)*(+1)FL&A正规表达式正规表达式举例课堂练习设计如下语言的正规表达式：FL&A正规语言正规语言（regularlanguage）归纳定义字母表上的正规语言归纳定

5、义如下：基础1{}和是正规语言2若a，则{a}是正规语言归纳1若L和R是正规语言，则LR是正规语言2若L和R是正规语言，则LR是正规语言3若L是正规语言，则L*是正规语言FL&A正规语言正规语言（regularlanguage）利用正规表达式定义对于字母表上的语言R，若存在上的正规表达式E，满足L(E)=R，则R是正规语言FL&A正规表达式的代数定律正规表达式的代数定律交换律和结合律零元和幺元分配律等幂律与闭包相关的定律代数定律的具体化用于发现和测试定律FL&A正规表达式的代数定律交

6、换律（commutativity）和结合律（associativeity）L+M=M+L(L+M)+N=L+(M+N)(LM)N=L(MN)幺元（identities）和零元（annihilators）+L=L+=LL=L=LL=L=FL&A正规表达式的代数定律分配律（distributivelaw）L(M+N)=LM+LN(M+N)L=ML+NL等幂律（idempotentlaw）L+L=LFL&A正规表达式的代数定律与闭包相关的定律(L*)*=L**=*=L+

7、=LL*=L*L（L+的定义）L*=L++与闭包相关的定律L?=+L（L?的定义）FL&A正规表达式的代数定律代数定律的具体化具体化：将正规表达式中的每个变量用单个符号替换.一般化：将具体表达式中的单个符号用变量表示.结论：正规表达式的一般形式所代表的任何语言与其对应的具体表达式的语言之间可以建立特定的对应关系.应用用于发现和测试关于正规表达式的定律FL&A正规表达式的代数定律代数定律的具体化定理：正规表达式的一般形式所代表的任何语言与其对应的具体表达式的语言之间存在如下对应关系:设E为正规表达

8、式，L1,L2,…,Lm为其中的变量.（这里，假设E中不含非变量符号，否则需推广）将每一Li替换为符号ai，得到对应E的一个具体表达式C.则对这些变量的任何实例语言S1,S2,…,Sm，L(E)中的任何串w可写成w=w1w2…wk的形式，其中wi是某一语言Sji(1jim)中的串，并且串aj1aj2…ajk属于语言L(C);另