3.3有限自动机 状态转换图实际上是有限自动机的 图形表示
3.3 有限自动机 状态转换图实际上是有限自动机的 图形表示
3.3.1确定的有限自动机DFA 1抽象地看，状态转换图由五个郁分组成： (1)有限个状态之集，犯作K写 (2)有限个输入符号组成的字母表，犯作 3)从Kx∑到K的转换函数fiK×∑→Kf(p,a)=q表示若 省前状态为P,且输入符号为a,刚进入下一个状态为q日 (4)S0∈K,初始（开始）状态； 5)若干个玲态之集：Z(三K) 由上述五个要素组成的五元式M=(K,∑，S0,Z)称为 一个确定的有限自动机(DFA:Deterministic Finite Automata) 由此可见，一DFA实际上是状态转换图的形式描迷（数学 定义)，状态转换图是DFA的几佰（图形）表示
3.3.1 确定的有限自动机DFA 1.抽象地看,状态转换图由五个部分组成: (1)有限个状态之集,记作K; (2)有限个输入符号组成的字母表,记作; (3)从K到K的转换函数 f: K→K. f(p,a)=q表示若 当前状态为p,且输入符号为a,则进入下一个状态为q; (4)S0K,初始(开始)状态; (5)若干个终态之集: Z( K ) 由上述五个要素组成的五元式 M=(K, , f,S0,Z )称为 一个确定的有限自动机 (DFA: Deterministic Finite Automata) 由此可见, 一DFA实际上是状态转换图的形式描述(数学 定义),状态转换图是DFA的几何(图形)表示
DFA的接受集 2.为定义DFA所接受（或识别的符号串集合，我们 先将其转换函数f的定义域拓广到KxΣ*： (1)f^(S,=S,S∈K, 2f(S,w=f(fS,,w,S∈K,a∈2w∈D, 由上面的定义可知，对于x∈*，f6,x)=t的含义是，当M从 状态s出发，依次扫描完x的各个符号后将进入状态t,即只 要f有定义f与的效果是一致的 我们称DFAM接受（或识别某符号串x∈，用状态转换图 来说，就是从初态S出发，经一恰好标有x的路径后可达 到某终态SeZ;用f描述就是：SeZ,fS,x)=S M的接受集我们把一DFAM所接受的符号串的全体称为 M的接受集，记为L(M),即L(MW={x|fSy∈Z,x∈}
DFA的接受集 2.为定义DFA所接受(或识别)的符号串集合,我们 先将其转换函数f 的定义域拓广到K* : (1)f^ (s,)=s, sK; (2)f^ (s,aw)=f^ ( f(s,a),w), sK,a,w*; 由上面的定义可知,对于x* ,f^(s,x)=t 的含义是,当M从 状态s出发,依次扫描完x的各个符号后将进入状态t.即只 要f有定义,f^与f的效果是一致的. 我们称DFA M接受(或识别)某符号串x* ,用状态转换图 来说,就是从初态S0出发,经一恰好标有x 的路径后可达 到某终态SZ ;用f^描述就是: SZ, f(S0,x)=S M的接受集 我们把一DFA M所接受的符号串的全体称为 M的接受集,记为L(M),即 L(M)={ x | f(S0 ,x) Z,x* }
确定的有限自动机 。 我们之所以把前面定义的有限自动机称为确定的 FA,是因为在状态转换的每一步，根据FA当前的 状态及扫描的输入字符，便能唯一地确定FA的下 一状态。在转换图上看，若=n,则任何结点所 引出的矢线至多有条，且矢线上的标记均不同。 ● 例如，P52图3-4所对应的DFA为 M=({R,U,S},{0,1},f,R,S》其中，f的定义如下： f(R,0)=U f(U,0)=U f(U,1)=S f(S,1)=S ● 由DFA与状态转换图的关系可知，构造状态转换 图的算法，同样适用于构造DFA。 ·实际上，我们可以证明，V正规文法G,DFAM, 使L(M)=L(G),反之亦然
确定的有限自动机 • 我们之所以把前面定义的有限自动机称为确定的 FA，是因为在状态转换的每一步，根据FA当前的 状态及扫描的输入字符，便能唯一地确定FA的下 一状态。在转换图上看，若||=n，则任何结点所 引出的矢线至多有n条，且矢线上的标记均不同。 • 例如，P52图3-4所对应的DFA为 M=({R,U,S},{0,1},f,R,{S}) 其中，f的定义如下： f(R,0)=U f(U,0)=U f(U,1)=S f(S,1)=S • 由DFA与状态转换图的关系可知，构造状态转换 图的算法，同样适用于构造DFA。 • 实际上，我们可以证明，正规文法G，DFA M， 使 L(M)=L(G)，反之亦然
3.3.2非确定的有限自动机 ·若在一左线性文法中含 有多个右部相同的产生 式，如A→Ua BUaC-→Ua.. X-→Ua, 或在一右线性文法中同 时含有形如 U-→aAU-→aBU→aC . U→aX的产生式， 图3-8NFA的状态转换图 在相应的状态转换图中， 央特买下状碧 就会出现这样的结点U, 不唯一，而是在状态集 它具有多条标记为同一 A,B,C ,中任选其一 ,具 输入符号a的矢线，如 有这种性质的FA称为非确定的 FA (NFA:Nondeterministic 右图所示 FA
3.3.2非确定的有限自动机 • 若在一左线性文法中含 有多个右部相同的产生 式，如 A→Ua B→Ua C→Ua X→Ua, • 或在一右线性文法中同 时含有形如 U→aA U→aB U→aC U→aX 的产生式， • 在相应的状态转换图中， 就会出现这样的结点U， 它具有多条标记为同一 输入符号a的矢线，如 右图所示 图3-8 NFA的状态转换图 由上图可知，在U状态下，输 入符号为a时，FA的下一状态 不唯一，而是在状态集 {A,B,C,…,X}中任选其一。具 有这种性质的FA称为非确定的 FA（NFA: Nondeterministic FA） U A B C X a a a a
非确定有限自动机的定义 在形式上，NFAM同样可用五元式定义： M=(K,∑，f,So,Z),其中，K,Σ，So,Z的含义同DFA,转换函 数f的定义为f:Kx∑→p(K),即将(Si,a)映射到K的一个子 集{Sk1,…,Skm} ·类似地，我们可把的定义域拓广到K×Σ*： (1)f(S,)={S}; (2)f(S,aw)=f(f(S,a),w) aeΣ，We∑* 再设f(S,a)={Sk1,.,Skm},且定义 这样，我们已把f 的定义域扩大到 f({S%S起，…，Skn},w)=Uf(Sk,w)） p(K)∑*。根据 则有： 类似的理由，我 们将对和不加 f(S.aw)=f(f(S.a).w)=Uf(S,.w) 区分
非确定有限自动机的定义 • 在形式上，NFA M同样可用五元式定义： M=(K,,f,S0,Z)，其中，K, ,S0,Z的含义同DFA,转换函 数f的定义为 f: K→(K),即将(Si,aj)映射到K的一个子 集{Sk1,…,Skm} • 类似地，我们可把f的定义域拓广到K* ： (1) f^(S,)={S}; (2)f^(S,aw)=f^(f(S,a),w) a,w*. 再设 f(S,a)= {Sk1,…,Skm} ,且定义 m i k m i k k k k f S aw f f S a w f S w f S S S w f S w i m i 1 ^ ^ ^ 1 ^ ^ ( , ) ( ( , ), ) ( , ) : ({ , , , }, ) ( , ) 1 2 = = = = = 则有 这样，我们已把f 的定义域扩大到 (K) *。根据 类似的理由，我 们将对f和f^不加 区分
NFA的接受集 a,b 。 对于x∈∑*若集合fS0,冲含有Z 中的元素（终态)，则说明，至 少存在一条从初态S到某一终态 的路径，此路径上的符号之连接 恰为x,此时，我们称为M所接 注意，NFA识别输入符号串 受 时有一个试探过程，为了能 所有为M所接受的符号串之集称 走到终态，往往要走许多弯 0 为NFAM的接受集（或识别集）， 路（带回溯），这影响了FA 的效率。 记作L(M).即L(M)={x/fSo, X门Z≠☑，X∈8 能否提高其工作效率就是我 例3.1给定M=(S,A,B,C,{a,b} 们下一小节讨论的课题。事 实上 f,S,{C),其状态转换图见右。由 对任一NFAM,总可 个AM1使 图可知M是一NFA。 L(M)=L(M0成立。这就是 M识别符号串ababb的路径为 NFA与DFA的等价性。 S(a)-→A(b)→B(a)-→A(b)-B(b) →C(接受)。（参见书中P60的表）
NFA的接受集 • 对于x*,若集合f(S0,x)中含有Z 中的元素（终态），则说明，至 少存在一条从初态S0到某一终态 的路径，此路径上的符号之连接 恰为x，此时，我们称x为M所接 受 • 所有为M所接受的符号串之集称 为NFA M的接受集（或识别集）， 记作 L(M).即 L(M)={x | f(S0, x ) Z , x} • 例3.1 给定M= ({S,A,B,C}, {a,b}, f , S ,{C}),其状态转换图见右。由 图可知M是一NFA。 • M识别符号串ababb的路径为 S(a)→A(b)→B(a)→A(b)→B(b) →C(接受)。(参见书中P60的表) S A B C a a,b a b b a a 注意，NFA识别输入符号串 时有一个试探过程，为了能 走到终态，往往要走许多弯 路（带回溯），这影响了FA 的效率。 能否提高其工作效率就是我 们下一小节讨论的课题。事 实上，对任一NFA M，总可 构造一个DFA M’，使 L(M’)=L(M)成立。这就是 NFA与DFA的等价性
3.3.3NFA与DFA的等价性 ·定理3.1对于字母表Σ上的任一NFAM,必存 在与M等价的DFAM? e 证明设M=(K,,fS0,Z)是Σ上的NFA,现构造Σ上 DFA M'=(K',∑，E',S0',z').方法如下： 1K'=p(K).为表示方便，设K某子集为{S1,S2,…,Si}, 记相应的状态为[S1,S2,…,S1].特别地，令So‘=[So】. 2.映射E'的定义： f'([S1,S2,…,Si],a)=[R1,R2,…,R]iff f({S1,S2,…,Si},a)={R1,R2,…,R} 3.M'的终态集 Z={[Sp,Sg…,Sr]I{Sp,Sq…,SxJ∩Z≠☑] 现在，我们证明，M'与等价.为此，对输入符号串x=的 长度进行归纳，以证明如下论断：
3.3.3 NFA与DFA的等价性 • 定理3.1 对于字母表上的任一NFA M，必存 在与M等价的DFA M’ • 证明 设 M=(K,,f,S0,Z) 是上的NFA，现构造上 DFA M’=（K’,,f’,S0’,Z’).方法如下： 1.K’=(K).为表示方便,设K某子集为{S1,S2,…,Si}, 记相应的状态为[S1,S2,…,Si].特别地,令S0’=[S0]. 2.映射f’的定义: f’([S1,S2,…,Si],a)=[R1,R2,…,Rj] iff f({S1,S2,…,Si},a)={R1,R2,…,Rj} 3.M’的终态集 Z={[Sp,Sq,…,Sr]|{Sp,Sq,…,Sr}Z} 现在,我们证明,M’与M等价.为此,对输入符号串|x|=n的 长度进行归纳,以证明如下论断:
包卫巧卫巧卫巧卫卫包斯包卫巧卫巧卫巧卫巧卫巧卫近 当x=0(即x=e)时，由于总有fSo,=S%,PS0,e=So',即 fS0,=S0,故论断成立.设对子长度小于或等于m的任何输入串x 论断均成立，现考虑输入串x,其中，x=m,a∈习 f(So',xa)=f(f(So',x),a) (设fS0,x)=S1,,S动 f(S1,,S/, (归纳假设 又设 fS,.,S,=R,,R/,由f的构造定义，有 fS1,.,S,0=RL,.…,l,从而， fS0,x)=R,,R台fS1,.,S,=R1,…,Bl 最后，若fS0,x)QZ≠O及由Z的定义，fS0,x)∈Z'.即 x∈LM台x∈LM)得证。 由于NFA与DFA是等价的，今后统称FA. 还应指出，确定化时所得的DFA的状态数是很大的，往往有许多无 用状态（即那些从初态$，不可达的状态或那些从其出发不能到达终 态的状态)，这些状态可从DFA中删除
当|x|=0 (即x=)时,由于总有 f(S0, )={S0}, f’(S0’, )=S0’ ,即 f’([S0’],)=[S0’],故论断成立.设对于长度小于或等于m的任何输入串x 论断均成立,现考虑输入串xa,其中,|x|=m,a, f’(S0’,xa)=f’(f’(S0’,x),a) (设 f(S0 ,x)={S1,…,Si}) =f’([S1,…,Si],a) (归纳假设) 又设 f({S1,…,Si},a)={R1,…,Rj}, 由f’的构造定义,有 f’([S1,…,Si],a)=[R1,…,Rj], 从而, f(S0,xa)={R1,…,Rj} f’([S1,…,Si],a)=[R1,…,Rj]. 最后,若 f(S0,x)Z及由Z’的定义,f’(S0,x)Z’.即 x L(M) x L(M’) 得证。 由于NFA与DFA是等价的,今后统称FA. 还应指出，确定化时所得的DFA的状态数是很大的，往往有许多无 用状态（即那些从初态S0不可达的状态或那些从其出发不能到达终 态的状态），这些状态可从DFA中删除
NFA确定化的例子 例3.2M=({So,S1},{a,b},f,So,s1) S f a b S0I{S0,S1}S1} S1|0 {S0,S1} M'=(K',{a,b),f',[Sol,{[Si],[So,SiB) fa b new state [1I[O 121 [So]I [SoS:] [S:l 1 [S]1[] [SoS:1 2 ISoS:]I [SoS:] 13 ba
NFA确定化的例子 例3.2 M=({S0,S1},{a,b},f,S0,{s1}) S0 S1 a b a|b b _f_|_a____ b___ S0 |{S0,S1} {S1} S1 | {S0,S1} M’=(K’,{a,b},f’,[S0],{[S1],[S0,S1]}) f’ | a b . | new state [] | [] [] | [S0] | [S0S1] [S1] | 1 [S1] | [] [S0S1] | 2 [S0S1]| [S0S1] [S0S1] | 3 1 2 3 a b b|a b