例(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