形式语言与自动机ppt课件.ppt

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

1、带-转移的有限自动机正则表达式右线性文法与正则集第三讲1CollegeofComputerScience&Technology,BUPT第四节有转换的NFA一、定义概念:当输入空串ε(无输入)时，也能引起状态的转移.例：输入“002”时的转移格局：q0q1q2012εε2CollegeofComputerScience&Technology,BUPT-NFA的形式定义一个-NFA是一个五元组A=(Q,T,,q0,F).有限状态集有限输入符号集转移函数一个开始状态一个终态集合q0QFQ与NFA的不同之处:Q(T)2Q3CollegeofCompute

2、rScience&Technology,BUPT-NFA如何接受输入符号串q1q0q2q3q5,+,–q4该-NFA可以接受的字符串如：3.14+.314–314.4CollegeofComputerScience&Technology,BUPT二、-闭包（closure）概念状态q的-闭包，记为-CLOSURE或ECLOSE，定义为从q经所有的路径可以到达的状态（包括q自身），如：q0q1q2012εε-CLOSURE(q0)={q0,q1,q2}-CLOSURE(q1)={q1,q2}-CLOSURE(q2)={q2}5CollegeofComput

3、erScience&Technology,BUPT状态子集I的ε-闭包：ε-CLOSURE(I)＝∪ε-CLOSURE(q)q∈I例：ε-CLOSURE({q1，q2})＝ε-CLOSURE(q1)∪ε-CLOSURE(q2)＝{q1，q2}Ia概念：对于状态子集IQ，任意a∈T，定义Ia如下：Ia=ε-Closure(P)其中P=δ（I，a）.即P是从I中的状态经过一条标a的边可以到达的状态集合6CollegeofComputerScience&Technology,BUPT例：I＝{q0，q1}，求I1I1＝ε-CLOSURE（δ（I，1））＝ε-CLOSURE（δ（{

4、q0，q1}，1））＝ε-CLOSURE（Φ∪{q1}）＝{q1，q2}q0q1q2012εε7CollegeofComputerScience&Technology,BUPT扩展转移函数适合于输入字符串设一个-NFA,:Q(T)2Q扩充定义:QT*2Q对任何qQ，定义：1(q,)=ECLOSE(q)2δ'(q，ωa)＝ε-CLOSURE(P)其中P＝{p

5、存在r∈δ'(q，ω)∧p∈δ(r，a)}注意：此时δ(q，a)δ'(q，a)，因为δ(q，a)表示由q出发，只沿着标a的路径所能到达的状态，而δ'(q，a)表示由q出发，沿着标a(包括ε

6、转换在内)的路径所能到达的状态.8CollegeofComputerScience&Technology,BUPTε-NFA中，δ与δ’函数的不同举例计算(q0,a)δ'(q0，ε)＝ε-CLOSURE(q0)＝{q0，q2}δ'(q0，a)＝ε-CLOSURE(δ(δ'(q0，ε)，a))＝ε-CLOSURE(δ({q0，q2}，a))＝ε-CLOSURE(δ(q0，a)∪δ(q2，a))＝ε-CLOSURE({q1}∪{q3})＝{q1，q2}∪{q3}＝{q1，q2，q3}同理：δ'(q0，aa)＝{q3}ε-CLOSURE(q0)＝{q0，q2}ε-CLOSURE

7、(q1)＝{q1，q2}ε-CLOSURE(q2)＝{q2}ε-CLOSURE(q3)＝{q3}9CollegeofComputerScience&Technology,BUPT三、-NFA的语言设一个-NFAM=(Q,T,,q0,F)定义M的语言：L(M)=ω

8、(q0,ω)F即满足δ'(q0，ω)含有F的一个状态10CollegeofComputerScience&Technology,BUPT四、有转换的NFA与无转换的NFA的等价1.-NFA<==>NFA具有转移的NFA是不具转移的NFA的一般情况,所以只要证明下面的定理即可:定理:如果L

9、被一个具有转移的NFA接收,那么L可被一个不具转移的NFA接收.证明思路:构造一个不具转移的NFA,证明其接收具有转移的NFA所接受的语言.11CollegeofComputerScience&Technology,BUPT从-NFA构造等价的无NFA设M=(Q,T,,q0,F)是一个-NFA,可构造一个无的NFAM1=(Q,T,1,q0,F1),对任何aT,1(q,a)=(q,a).(注意δ与δ’的区别与联系。而δ1和δ1’是相等的。F1＝F∪{q0}若ε-CLOSURE(