《离散数学》课程PPT教学课件（讲稿）第11章 形式语言和自动机初步（11.2-11.3）有穷自动机、有穷自动机和正则文法 的等价性

112有穷自动机 ■确定型有穷自动机(DFA) ■非确定型有穷自动机NFA) ■带转移的NFA(2NFA)

1 11.2 有穷自动机 ◼ 确定型有穷自动机(DFA) ◼ 非确定型有穷自动机(NFA) ◼ 带ε转移的NFA(ε-NFA)

确定型有穷自动机 定义确定型有穷自动机(DFA是一个有序5元组 M=(QE,qF),其中 (1)状态集合Q:非空有穷集合 (2)输入字母表∑:非空有穷集合 (3)状态转移函数6:Qx∑→Q (4)初始状态q∈Q 控制器 (5)终结状态集FcQ n

2 确定型有穷自动机 定义 确定型有穷自动机(DFA)是一个有序5元组 M = Q,Σ,δ,q0 ,F , 其中 (1) 状态集合Q: 非空有穷集合 (2) 输入字母表Σ: 非空有穷集合 (3) 状态转移函数δ:QΣ→Q (4) 初始状态 q0Q (5) 终结状态集 FQ 控制器 a1 a2 … ai … an

DFA接受的语言 把δ扩张到Qx*上6:QX→Q,递归定义如下 Vq∈Q,a∈和w∈∑ d(, a=q δ(q,w)=0(6(q,形),a) 定义Vw∈x,如果*(qw)∈F,则称M接受 M接受的字符串的全体称作M接受的语言,记作 LM,即 L(M)={w∈|δ(q)∈F}

3 DFA接受的语言 把δ扩张到QΣ*上 δ * :QΣ*→Q, 递归定义如下 qQ, aΣ和wΣ* δ * (q,ε)=q δ * (q,wa)= δ(δ * (q,w),a) 定义 wΣ* ,如果δ * (q0 ,w)F, 则称 M接受w. M接受的字符串的全体称作M接受的语言,记作 L(M), 即 L(M)={ wΣ* | δ * (q0 ,w)F }

DFA接受的语言(续) 例1M=({91h,{a,0,9mq) 6(q0,a)=q1,o(q1,a)=q0 q1 501gn)= n为奇数 q,m为偶数 6tm,a)={9n,n为奇数 19 n为偶数 L(M={a2k+k∈N

4 DFA接受的语言(续) 例1 M= {q0 , q1 },{a}, δ,q0 ,{q1 } δ(q0 , a)=q1 , δ(q1 , a)=q0 L(M)={a 2k+1 | kN}    =  为偶数 为奇数 0 1 0 q , n q , n δ (q ,a ) n    =  为偶数 为奇数 1 0 1 q , n q , n δ (q ,a ) n

非确定型有穷自动机 定义非确定型有穷自动机(NFA) M=〈Q,Σ,δ,qF), 其中Q,∑,qF的定义与DFA的相同,而 6:Q×→P(Q

5 非确定型有穷自动机 定义 非确定型有穷自动机 (NFA) M =〈 Q,Σ,δ,q0 ,F 〉, 其中 Q,Σ, q0 , F 的定义与 DFA 的相同, 而 δ: Q Σ→P(Q)

实例 例2一台NFA q1 q24 94 0{q0,q3 {q2}{q4{q4 {qo,q1}{q2}{q2}z{q4 @@4O° 0,1

6 实例 δ →q0 q1 *q2 q3 *q4 0 1 {q0 , q3 }  {q2 } {q4 } {q4 } {q0 , q1 } {q2 } {q2 }  {q4 } 例2 一台NFA

NFA接受的语言 6*:Q→Q递归定义如下:∨q∈Q,m∈∑和w∈∑ δ(q,e)={(q} δ*(q,wao=∪6(p,a) P a,7 定义V∈x,如果8*(q,)nF,则称M接受w M接受的字符串的全体称作M接受的语言,记作 L(M,即 L(M={w∈|δ°(q0,w)nF≠x}

7 NFA接受的语言  ( , ) ( , ) p q w p a    δ * :QΣ*→Q 递归定义如下: qQ, aΣ 和 wΣ* δ * (q,ε)={q} δ * (q,wa)= 定义 wΣ* ,如果δ * (q0 ,w)∩F≠, 则称M接受w. M接受的字符串的全体称作M接受的语言,记作 L(M), 即 L(M)={ wΣ* | δ * (q0 ,w)∩F≠ }

例2(续) 风 W°+(g0,w) {q0,q1 0{90g3} 101{q0,9} 1011(, 923 10110{qo,g2,q3} L(G)={x00y,x11y|x,y∈{0,1}*

8 例2 (续) L(G) = { x00y, x11y | x,y{0,1}* } w δ * (q0 ,w) 1 10 101 1011 10110 {q0 , q1 } {q0 , q3 } {q0 , q1 } {q0 , q1 , q2 } {q0 , q2 , q3 }

DFA与NFA的等价性 定理对每一个NFAM都存在DFAM使得 L(M=L(M 用M=(Q,x,8’q,F〉模拟M=(Q,,,0,F) Qy=P(Q,q0′={q0 F={A∈Q|AnF≠} A∈Q和a∈∑, 6(4,a)=∪6(,a) p∈A

9 DFA与NFA的等价性 用M=Q ,Σ,δ,q0 ,F 模拟 M=Q,Σ,δ,q0 ,F  Q=P(Q), q0 ={q0 } F={ AQ | A∩F≠} AQ 和 aΣ,  p A A a p a  ( , ) =  ( , ) 定理 对每一个NFA M 都存在DFA M 使得 L(M)=L(M )

模拟实例 NFAM DFAM 0 0 9090, 913 g03 go390,1 go q1{q2} {q1} {q2} q 幺{q2 {q0q1}{90gnq23{o go,92)2o,13 g03 {qn42}{q2} 0 0 →④ @{ 10

10 模拟实例 NFA M DFA M δ 0 1 →q0 q1 *q2 {q0 , q1 } {q0 } {q2 }    δ 0 1 →{q0 } {q1 } *{q2 } {q0 ,q1 } *{q0 ,q2 } *{q1 ,q2 } *{q0 ,q1 ,q2 }  {q0 , q1 } {q0 } {q2 }    {q0 ,q1 ,q2 } {q0 } {q0 ,q1 } {q0 } {q2 }  {q0 ,q1 ,q2 } {q0 }  