资源描述：
《编译原理第3章(3).ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、§3.3有限自动机(FA)§3.3.1确定的有限自动机（DFA）一个DFA有以下五个元素组成:DFAM=（K，∑，f，S0，Z）其中K：状态的集合（有限个状态）∑：允许输入的字符的集合Vtf：状态转换函数，单值函数K×∑→KS0：初始状态S0∈KZ：终止状态集ZKf(Si,a)=Sj1北京交通大学 于双元讨论：(1)①确定性f是单值函数从某一状态读一字符的下一状态唯一确定②有限的K集合元素个数有限(2)f定义的推广f单值函数K×∑→KK×Σ*→KΣ*=∑+∪{ε}记为ｆ^①ｆ^(S,ε)=S②ｆ^(S,aω)=ｆ^(f(S,a),ω)a∈∑,ω∈
2、Σ*f(S,a)=Sk=ｆ^(Sk,ω)=…=StSt∈Kｆ^:K×Σ*→K单值映射2北京交通大学 于双元③ｆ^是在Σ*上定义,f是在∑上定义,ｆ^包含f,将ｆ^和f合并为一个f,记为f(推广后)(3)有限自动机的功能:识别句子L(M)={}x
3、f(S0,x)∈Z,x∈Σ*特别:f(So,ε)=So且So∈Z称ε可为DFAM识别S03北京交通大学 于双元(4)DFA可非形式地表示成状态图和状态矩阵例:DFAM=({S,A,B,C},{0,1},δ,S,{S})δ(S,0)=Bδ(S,1)=Aδ(A,0)=Cδ(A,1)=Sδ(B,0)=Sδ(B,
4、1)=Cδ(C,0)=Aδ(C,1)=BSABC10100101状态输入0输入1SBAACSBSCCAB101011δ(S,101011)=δ(δ(S,1),01011)=δ(A,01011)=δ(C,1011)=δ(B,011)=δ(S,11)=δ(A,1)=S4北京交通大学 于双元(5)正则文法G一定DFAM反之L(G)L(M)5北京交通大学 于双元§3.3.2非确定的有限自动机(NFAM′)一个NFAM′有以下五个元素组成,DFAM′=(K′,Σ,f′,S0′,Z′)其中:K′:状态的集合(有限状态)Σ:允许输入的字符集合f′:状态转换函数
5、,多值函数,K′×Σ→2k’(K的所有子集的集合)f(Si,a)={Sk,St…}S0:初始状态S0∈K′Z:终止状态集ZK′Si……aaaSkStSr6北京交通大学 于双元讨论:1)①不确定:f′是多值函数,一对多②有限:K′有限2)f′定义推广到Σ*上,K′×Σ*→2k’,记为ｆ^′①ｆ^′(S,ε)={S}②ｆ^′(S，aw）=ｆ^′(f′(S,a),w)设：f′(S,a)={S1,S2,…..,Sk}=ｆ^′({S1,S2,…..,Sk},w)=∪ｆ^′(Si,w)i=1k③将ｆ^′和f′合并为一个f′,记为f′7北京交通大学 于双元(3
6、)NFAM′所确定的语言L(M′)={x
7、f′(S0′,x)∩Z≠Ø,x∈Σ*}(4)NFAM′通常用状态转换图来表示例:NFAM′=({S,A,B,C},{a,b},f′,S,{C})符号串ababb可由此NFAM′所识别.SBCAaaaabba,b8北京交通大学 于双元§3.3.3DFAM与NFAM′的等价性1、对于∑上NFAM′一定DFAML(M′)L(M)2、方法:确定化①读ε不动作的NFAM′②读ε动作的NFAM′最小化9北京交通大学 于双元(1)读ε不动作的NFAM′的确定化问题：设有一NFAM′=(K′,∑,f′,S0′,Z′)现构
8、造一∑上的DFAM=(K,∑,f,S0,Z)使L(M′)=L(M)①K由K’的全部子集组成K=2K’特别S0=[S0′]②映射f的定义当且仅当f′({S1,S2,…Si},a)={R1,R2,…Rj}时,Si、Rj∈K′则f([S1,S2,…Si],a)=[R1,R2,…Rj]qiqjf(qi,a)=qjK′×Σ→2k’10北京交通大学 于双元③DFAM的终态集Z的定义是:M的某一状态[R1,R2,…Rj],其中至少含有一个M′的一个终态则[R1,R2,…Rj]∈ZZ={[R1,R2,…,Rj]
9、[R1,R2,…,Rj]∈K且{R1,R2,…,R
10、j}∩Z′≠Ø}11北京交通大学 于双元abq0=[s0]q3q0q1=[s1]Øq2q2=[s2]ØØq3=[s0,s1]q3q4q4=[s0,s2]q3q0q5=[s1,s2]Øq2q6=[s0,s1,s2]q3q4Øf′({s0},a)={s0,s1}f(q0,a)=q3bq0q1q3q2ababq4abq5bq6abS0S1S2a,bab12北京交通大学 于双元(2)读ε动作的NFAM′的确定化K′×Σ∪{ε}→2k’定义:(1)状态q的ε闭包ε_closure(q)q∈K′①q∈ε_closure(q)②qε{ε}到达的状态均属于ε_c
11、losure(q)(2)状态集P的ε闭包ε_closure(P)PK′①若q∈P,则q∈ε_closure(P)②若q∈P,qε{ε}到
