第第 3 3 章章 自动机基础自动机基础3.1 3.1 正规语言及其描述方法正规语言及其描述方法【内容提要内容提要】 自动机自动机 是一种语言模型，是语言的一种识别是一种语言模型，是语言的一种识别工具，其中的工具，其中的 有限自动机有限自动机(finite automata(finite automata）FAFA 被用来处理被用来处理 正规语言正规语言，后者是编译程序设计中后者是编译程序设计中词法词法分析分析的对象。的对象。3.2 3.2 有限自动机的定义与分类有限自动机的定义与分类3.3 3.3 有限自动机的等价变换有限自动机的等价变换1,21,23.4 3.4 有限状态自动机的实现问题有限状态自动机的实现问题3.5 3.5 正规语言描述方法间的相互转换正规语言描述方法间的相互转换3.1 3.1 正规语言正规语言及其描述方法及其描述方法 【定义定义】 正规语言正规语言是指由是指由正规文法正规文法定义的语言；定义的语言；程序设计语言中的程序设计语言中的单词单词，大都属于此种语言。，大都属于此种语言。正规语言正规语言有三种等价的表示方法：有三种等价的表示方法： 正规文法正规文法 正规式正规式 有限自动机有限自动机正规文法正规文法是指仅有三种形式的产生式：是指仅有三种形式的产生式： A - A - aBaB A - a A - A - a A - 【例例3.13.1】 G(Z) G(Z)：A -A -aAaA| | A=A= ; ; A A=aAaA=aaAaaA=aaaAaaaA=a=an n ,n0,n0 L(G)= aL(G)= an n | n0 | n0 正规文法正规文法正规语言正规语言 正规语言判定示例正规语言判定示例: :【例例3.23.2】 L1 = L1 = a am mb bn n| m0 ,n1 , | m0 ,n1 , 正规语言正规语言 ? ? 可由正规文法定义：可由正规文法定义： G1(S): S - G1(S): S - aS|bAaS|bA ; A - ; A - bAbA| | L1 L1 是正规语言。是正规语言。 【例例3.33.3】 L2 =( L2 =(ab)ab)n n| n1 , | n1 , 正规语言正规语言 ? ? 可由正规文法定义：可由正规文法定义： G2(S): S - G2(S): S - aAaA ; A - ; A - bBbB ; B - ; B - aAaA| | L2 L2 是正规语言。是正规语言。 【例例3.43.4】 L3 = L3 =a an nb bn n| n0 , | n0 , 正规语言正规语言 ? ? 不能由正规文法定义不能由正规文法定义( (正规文法无法描述正规文法无法描述a a和和b b数量数量上相等！上相等！) )： L3 L3 不是正规语言！不是正规语言！ 3.1.1 3.1.1 正规语言正规语言的的正规式正规式表示法表示法 正规式正规式 是指由字母表中的符号，通过以下是指由字母表中的符号，通过以下三种运算三种运算( (也可以使用圆括号也可以使用圆括号) )连接起来构成的表达式连接起来构成的表达式 e e ： 连接连接 ( ( . .) ) 或或( ( | | ) ) 闭包闭包( ( + +，* * ) ) 设设 val(e)val(e), ,L(eL(e) ) 分别表示正规式分别表示正规式 e e 的的值值和和语言，语言，则：则： L(e)= x| x=L(e)= x| x=val(eval(e)即即 正规式正规式表示的表示的语言语言是该是该正规式所有值的集合正规式所有值的集合( (正规集正规集) )。例： 正规式正规式 正规式的正规式的 值值 ab.cdeab.cde abcdeabcde ab|cdeab|cde abab , , cdecde a a+ +a ,a ,aaaa , ,aaaaaa , , ,a ,an n , ,a a* *,a,aa,aaa,an, 正规式正规式表示表示正规语言正规语言示例：示例：展开：展开： L(e3) = L(e3) = ababn nc c, , b bn n | n0 | n0 ， L(e2) = (L(e2) = (ab)ab)n n| n1 | n1 ， e2=(e2=(abab) )+ + e3= e3= abab* *c|bc|b* * L L（e1e1）= = a am mb bn n| m0 ,n1 | m0 ,n1 ， e1= a e1= a* *b b+ + = = b,ab,bb,aaab,aab,abb,aabbb,ab,bb,aaab,aab,abb,aabb, , = = ab,abab,ababab,ababababab,abab,ababab,abababab, , = = ac,abc,abbc,abbbcac,abc,abbc,abbbc, ,; ; , ,b,bb,bbbb,bb,bbb, , 【例例】：3.1.2 3.1.2 正规语言正规语言的的有限自动机有限自动机表示法：表示法： L3= L3= ababn nc c ,b,bn n|n0 |n0 ， L2= (L2= (ab)ab)n n| n1 | n1 ， L1= L1= a am mb bn n| m0 ,n1 | m0 ,n1 ，+ + b- -ab+ + b- -aa+-abcbb-FA1:FA1:FA2:FA2:FA3:FA3: 初看起来，有限自动机是带标记的有向图！初看起来，有限自动机是带标记的有向图！1,2,3,4 1,2,3,4 状态集状态集; ; 其中：其中： +(+(开始状态开始状态) )；-(-(结束状态结束状态) )a,b,c a,b,c 字母表；字母表； (1,a)=2 (1,a)=2 变变换换 ( ( 或或 ););有限自动机有限自动机表示法说明表示法说明： a L3= L3= ababn nc c ,b,bn n|n0 |n0 +-abcbb-FA3:FA3: 一个一个 FAFA，若存在一条从某开始状态若存在一条从某开始状态 i i 到到某结束状某结束状态态 j j 的通路，且这条通路上所有边的标记连成的符号的通路，且这条通路上所有边的标记连成的符号串为串为 ，则，则 就是一个句子；就是一个句子；所有这样的所有这样的 的集合，的集合，就是该就是该 FA FA 表示的语言表示的语言。【图符说明图符说明】：【运行机制运行机制】：（ 表示表示1 1状态遇符号状态遇符号a a变到变到2 2状态状态, ,) )；e =e = abab* *c|bc|b* * G(S): S- G(S): S- aA|bBaA|bB| | ，A - A - bA|bA|c c ，B -B - bBbB| | 正规语言的三种表示法综合示例：正规语言的三种表示法综合示例：【例例3.53.5】 L = L = ababn nc c, , b bn n| n0 ,= a,b,c| n0 ,= a,b,c； 【注注】 凡是能由上述三种方法表示的语言，一定凡是能由上述三种方法表示的语言，一定是是正规语言正规语言；反之，凡是不能由上述三种方法表示；反之，凡是不能由上述三种方法表示的语言，一定的语言，一定不是正规语言不是正规语言。1. 1. 正规文法描述：正规文法描述： 2. 2. 正规式描述正规式描述: :3. 3. 有限自动机描述：有限自动机描述：+-abcbb-FAFA: :表示可接受表示可接受空串空串！ 3.2.1 3.2.1 有限自动机的定义有限自动机的定义状态状态 i i 遇符号遇符号 a,a,变换为状态变换为状态 j j 3.2 3.2 有限自动机的定义和分类有限自动机的定义和分类 ：变换（二元函数）：变换（二元函数）：Q Q( (有限状态集有限状态集); ); i ij ja a或或【定义定义】 有限自动机是一种数学模型，用于描述正有限自动机是一种数学模型，用于描述正规语言规语言, ,可定义为可定义为五元组五元组： (i,a(i,a）=j=j其中：其中：i,jQ, i,jQ, aa+ ; ;F F( (结束状态集结束状态集, ,F F Q Q ）；）；S S( (开始状态集开始状态集, ,S S Q Q）；( (字母表字母表) )；【含义含义】FA=( Q,S,F,FA=( Q,S,F, ) )L(FA)L(FA)= x| i= x| i FA FA 存在一条从某初始状态存在一条从某初始状态 i i 到到某结束状态某结束状态 j j 的的连续变换连续变换，且，且每次变换每次变换( (=) )的边标记连成的符号串恰的边标记连成的符号串恰好为好为 x x ；称称x x为为FAFA接受，否则拒绝接受，否则拒绝。 3.2.2 3.2.2 有限自动机怎样描述语言有限自动机怎样描述语言 令令 L(FA) L(FA)为自动机为自动机FAFA所描述的正规语言；则所描述的正规语言；则如如 右图有限自动机：右图有限自动机：= x x+-abcbb-设设 x=ax=a1 1 a a2 2a an n ， a ai i+ a a1 1=i i1 1i ia a2 2=i i2 2a an n=j j则有则有即：即：含义是含义是: :j , j , xx* * , ,iS,jFiS,jF 则则 L(FA)L(FA)的的识识别别过程如下所示：过程如下所示： L(FA) L(FA)的生成的生成( (或识别或识别) )过程示例：过程示例：+-abcbb-.第一条通路：第一条通路：FA1FA1=b b+ + +=a a =b b=c c+ +=a a =b b =b b=c c.第二条通路：第二条通路：FA2FA2+ += =a a =c c+ +=b b =b b+ + L(FA)=L(FA)=ababn nc c, , b bn n| n0 | n0 L(FA1)= L(FA1)= ababn nc c| n0 | n0 L(FA2)= L(FA2)= b bn n| n0 | n0 因而因而接受空串的接受空串的 FAFA的典型特征！的典型特征！ 3.2.3 3.2.3 有限自动机有限自动机的的两种表现两种表现形式形式【例例3.63.6】有限自动机有限自动机 ：FA=( Q,S,F,FA=( Q,S,F, ) ) 其中其中: : Q Q=1,2,3,4,=1,2,3,4,=a,b,c, =a,b,c, S S=1,2, =1,2, F F=3=3，44 FAFA 的两种表现形式：的两种表现形式： 状态图状态图: : ：(1,a)=2;(1,b)=4(1,a)=2;(1,b)=4；(2,b)=2(2,b)=2； (2,c)=3(2,c)=3；(2,(2, )=3)=3；(4,b)=4(4,b)=4； 变换表变换表: : 变换表结构变换表结构：行行( (状态状态),),列列( (符号符号),),表项表项( (变换后状态变换后状态) ) +-abcb bb b- + +4332421 12 23 34 4a a b bc c + +- - -+ +开始状态开始状态结束状态结束状态a ab b【例例3.73.7】 A= ab A= abn nc,(ab)c,(ab)n n|n0 |n0 或或：变换函数不单值，：变换函数不单值，如如一一：开始状态不唯一：开始状态不唯一, ,不好用不好用! !( ( (1,a)=(2|4) ),(1,a)=(2|4) ),也不好用！也不好用！方法一方法一：联合式联合式方法二方法二：组合式组合式1 1比较：比较：二二：带有：带有 边，还是不好用边，还是不好用! !有好用的吗有好用的吗?!?!FAFA的构造：的构造： 有限自动机的构造示例有限自动机的构造示例1 1+ab bc-+ -+ -ab b+ -+ -ab b+ab bc-或或+ab bc-【例例3.73.7】构造正规语言构造正规语言+ab bc-a ab ba a- A=ab A=abn nc,(ab)c,(ab)n n|n0 |n0 +ab bb b-b bcb b-aa-ccDFA:DFA: 有限自动机的构造示例有限自动机的构造示例2 2 确定的有确定的有限自动机如右图限自动机如右图所示：所示：方法三方法三：确定式确定式+ab bb b-b bcb b-aa-ccDFA:DFA: 确定的有限自动机确定的有限自动机(DFA)(DFA)特征特征：开始状态唯一开始状态唯一; ; 变换函数单值；变换函数单值；不带不带 边。边。 非确定的有限自动机非确定的有限自动机(NFA)(NFA) 带有带有 边的边的非确定的有限非确定的有限自动机自动机( ( NFA)NFA) 不带有不带有 边的边的非确定的有限非确定的有限自动机自动机( NFA)( NFA)- - 不能全部具备上述特征者！不能全部具备上述特征者！ 3.2.4 3.2.4 有限自动机的分类有限自动机的分类 有限自动机的分类示例有限自动机的分类示例+ab b- b b FA1FA1+ +ab b-b bb b-【例例3.83.8 】试分别指出下述有限自动机的分类情况：试分别指出下述有限自动机的分类情况：FA2FA2+ab bc- FA3FA3ab bc c-+ +c cc c+ +ab bc c-+ +c cb bFA5FA5结论：结论：DFADFA: FA2: FA2NFANFA: FA4,FA5: FA4,FA5FA1,FA3 (FA1,FA3 ( NFA)NFA)FA4FA4( ( NFA)NFA) 练习题：练习题：【习题习题3.13.1】解释下列词语：解释下列词语： 正规文法，正规语言，有限自动机；正规文法，正规语言，有限自动机； 确定的有限自动机，非确定的有限自动机。确定的有限自动机，非确定的有限自动机。【习题习题3.23.2】P64_7P64_7【习题习题3.33.3】P64_9P64_9【习题习题3.43.4】给定正规语言，构造有限自动机：给定正规语言，构造有限自动机： 无符号整数无符号整数 （正规式为（正规式为 e=e=dddd* *） 标识符集标识符集( (正规式为正规式为 e= e= ( (|d)|d)* * ) ) A= A= a an n,ba,ban n |n0 |n0 谢谢收看！谢谢收看！正规式描述语言的简单运算例：正规式描述语言的简单运算例：1.1.L(a)=aL(a)=a2.2.L(a|b)=L(a)+L(b)=a,bL(a|b)=L(a)+L(b)=a,b3.3.L(a.b)=L(a).L(b)=a.b=L(a.b)=L(a).L(b)=a.b=abab 4.4.L(a(a|b)c )=L(a).L(a|b).L(c)L(a(a|b)c )=L(a).L(a|b).L(c) =a.a,b.c= =a.a,b.c=aac,abcaac,abc 5. L(b5. L(b* *)=(L(b)=(L(b)* *=b=b* *=,b,bb,bbb,b,bb,bbb, , = = b bn n |n0 |n0 6. 6. L(abL(ab* *)=L(a).L(b)=L(a).L(b* *)=)=a,ab,abba,ab,abb, =ab =abn n|n0|n07. L(a|b)7. L(a|b)* *)= (L(a|b)= (L(a|b)* *=a,b=a,b* * 即即: :由由a,ba,b组成的所有符号串组成的所有符号串( (包括空串包括空串) )集合。集合。 ET | | E + T | | E - TTF | | T * F | | T / FFi | ( E )| ( E )P:P:基本图形库基本图形库 =. .+ + =+ +A = . .+ + = + +=*, =+ , =.* , =.+ , =l* , =l+ , =.l+ ，=.l* = =. .