《程序设计语言与编译》课程PPT教学课件（高职）第十一讲 自动机

例(i+*i) EtE|+

E （ E ） E * E E + E i i i E （ E ） E + E E E i i i * 例（i+i*i ）

第二节自动机 文法是语言的生成系统,而自动机是语 言的识别系统。自动机分为图灵机、线 性有界自动机、下推自动机、有限自动 机

第二节 自动机 文法是语言的生成系统，而自动机是语 言的识别系统。自动机分为:图灵机、线 性有界自动机、下推自动机、有限自动 机

有限自动机的定义 1.确定的有限自动机 DFA MO=(Σ,S,sO,F,8) 6:S×∑→S

一. 有限自动机的定义 1. 确定的有限自动机 DFA Md=(,S,s0,F,)  :S →S

例∑={0,1}0是初态 S={s0,s1,s2,s3} F={s0} δ(0,0=S2 50,1)=l δ(s1,0=s38(s1,1)=s0 6(S2,0=S0 (S2,1)=s3 (s3,0)=s18(s3,1)=s2

例: ={0,1} s0是初态 S={s0,s1,s2,s3} F={s0} (s0,0)=s2 (s0,1)=s1 (s1,0)=s3 (s1,1)=s0 (s2,0)=s0 (s2,1)=s3 (s3,0)=s1 (s3,1)=s2

2.非确定的有限自动机 NFA MnE(Σ,S,SO,F,8) 8S×∑→→2S

2. 非确定的有限自动机 NFA Mn=(,S,s0,F,)  :S →2S

例∑=(0,1}s0是初态 S={s0,s1,s2,s3,s4} F={s2,s4 δ(0,0)={s0,s3}8(s0,1)={s0,s1} δ(S1,0)= 6(S1,1)={S2} (S2,0)={s2} 6(S2,1)={s2} (S3,0={s4} δ(S3,1)=d δ(s4,0)={s4} δ(4,1)={s4}

例: ={0,1} s0是初态 S={s0,s1,s2,s3,s4} F={s2,s4} (s0,0)={s0,s3} (s0,1)={s0,s1} (s1,0)= (s1,1)={s2} (s2,0)={s2} (s2,1)={s2} (s3,0)={s4} (s3,1)= (s4,0)={s4} (s4,1)={s4}

二.有限自动机的表示 1.状态转换矩阵 若|S|=m2|=n 则可以用一个mxn的矩阵表示SxΣ的状态 变换

二. 有限自动机的表示 1. 状态转换矩阵 若│S│= m,││=n 则可以用一个mn的矩阵表示S的状态 变换

DFA S 0 2 S S S3 52 SO S3 S2 F={s0}

S  0 1 s0 s1 s2 s3 s2 s1 s3 s0 s0 s3 s1 s2 DFA F={s0}

2NFA522 S 0 s0,s3} d {S2} 2 {S2} {S2} {s4} S4 {s4} F={S2,s4}

S  s0 s1 s2 s3 s4 0 1 {s0,s3} {s0,s1}   {s2} {s2} {s2} {s4} {s4} {s4} NFA F={s2,s4}

2状态转换图 初态 终态 2所有弧上字符的集合

2. 状态转换图 初态: 终态: :所有弧上字符的集合 