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

实例 例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≠ }