《第三章自动机基础(1)》由会员分享，可在线阅读，更多相关《第三章自动机基础(1)（23页珍藏版）》请在金锄头文库上搜索。
1、 产生式形式为：产生式形式为：xAyxAy - - x x y y 产生式形式为：产生式形式为：A-A-aBaB , A-a , A- , A-a , A- 产生式形式为：产生式形式为：A - A - 形式语言分为形式语言分为四类四类，由文法，由文法产生式产生式的的形式不同形式不同而区别，而区别， 2 2 型语言型语言 由由 2 2型文法型文法定义定义 1 1 型语言型语言 由由 1 1型文法型文法定义定义 0 0 型语言型语言 由由 0 0型文法型文法定义定义 产生式形式为：产生式形式为： - - 3 3 型语言型语言 由由 3 3型文法型文法定义定义又称又称 无限制文法无限制文法/ /语言
2、语言 ！又称又称 上下文有关文法上下文有关文法/ /语言语言 ！又称又称 上下文无关文法上下文无关文法/ /语言语言 ！又称又称 正规文法正规文法/ /语言语言 ！【注注】 四类语言为四类语言为 包含关系，且有包含关系，且有 L0 L1 L2 L3；编译处理中，主要应用编译处理中，主要应用后两种文法后两种文法！2.72.7 形式语言的分类问题形式语言的分类问题A,B VA,B VN N，aVaVT T，(x y(x y) )(V(VN N+V+VT T) )* *令：令：第第 3 3 章章 自动机基础自动机基础3.1 3.1 正规语言及其描述方法正规语言及其描述方法【内容提要内容提要】 自动机
3、自动机 是一种语言模型，是语言的一种识别是一种语言模型，是语言的一种识别工具，其中的工具，其中的 有限自动机有限自动机(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 正规语言正规语
4、言及其描述方法及其描述方法 【定义定义】 正规语言正规语言是指由是指由正规文法正规文法定义的语言；定义的语言；程序设计语言中的程序设计语言中的单词单词，大都属于此种语言。，大都属于此种语言。正规语言正规语言有三种等价的表示方法：有三种等价的表示方法： 正规文法正规文法 正规式正规式 有限自动机有限自动机正规文法正规文法是指仅有三种形式的产生式：是指仅有三种形式的产生式： 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,
5、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 , 正规语言正规语言 ? ? 可由正规文法定义：可由正规文法定
6、义： 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 正规语言正规语言的的正规式正规式表示法表示法 正规式正规式 是指由字母表中的符号，通过以下是指由字母表中的符号，通过以下
7、三种运算三种运算( (也可以使用圆括号也可以使用圆括号) )连接起来构成的表达式连接起来构成的表达式 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 abcdeab
8、cde 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 ,n
9、1 ， e1= a e1= a* *b b+ + = = b,ab,bb,aaa,aab,aba,abbb,ab,bb,aaa,aab,aba,abb, , = = 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
10、 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 n
11、c 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):
12、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
13、. 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+
14、 ; ;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 有限自动机怎样描述语言有限自动机怎样描述语
15、言 令令 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
16、=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
17、,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- + +4
18、332421 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的构造：的构造： 有限自动机的构造示
19、例有限自动机的构造示例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)特征特征：开始状态唯一开始状态
20、唯一; ; 变换函数单值；变换函数单值；不带不带 边。边。 非确定的有限自动机非确定的有限自动机(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 】试分别指出下述有限自动机的分类情况：试分别指出下述有限自动机的分类情况：FA2
21、FA2+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】给定正规语言，构造有限自动机：给定正规语言，构造有限自动机： 无
22、符号整数无符号整数 （正规式为（正规式为 e=e=dddd* *） 标识符集标识符集( (正规式为正规式为 e= e= ( (|d)|d)* * ) ) A= A= a an n,ba,ban n |n0 |n0 第第2 2章章 习题解答：习题解答：【习题习题2.52.5】P27_2.5 ; P27_2.5 ; 证明下面文法是二义性文法证明下面文法是二义性文法 S-S-iSeSiSeS | |iSiS |i |i【证证】因为句型因为句型 iiSeSiiSeS 有下述两棵不同的语法树：有下述两棵不同的语法树：S Si S e Si S e Si Si SS Si Si Si S e Si S e
23、 S和和所以所属所以所属文法是二文法是二义性文法！义性文法！【习题习题2.6 2.6 】G(S): S-G(S): S-aAcBeaAcBe ; A- ; A-Ab|bAb|b ; B-d ; B-d 证明证明 = aAbcde 是一个句型；是一个句型； 画出句型画出句型 的语法树；的语法树； 指出句型指出句型 的短语、简单短语和句柄。的短语、简单短语和句柄。第第2 2章章 习题解答：习题解答：【习题习题2.122.12】消除下述文法的直接左递归：消除下述文法的直接左递归： G(S): E-E+T|E-T|T G(S): E-E+T|E-T|T 【解解】 消除直接左递归公式：消除直接左递归公式
24、：整理整理: : E - E + T | E T | TE - E + T | E T | T 有有 G(S): E - T G(S): E - T T T A - A A - A | | A - A - A - A - A, A- A, A- A | A |或或G(S): E - T G(S): E - T EEE- E- T T E | E | 令：令： = = +|- +|-E - E E - E T | T T | T第第2 2章章 习题解答习题解答5 5：【习题习题2.112.11】化简下述文法：化简下述文法： G(S): S-G(S): S-aSab|bABaSab|bAB ; A
25、- ; A-bB|abB|a ; B- ; B-aA|baA|b C- C-abB|baAabB|baA ; D- ; D-Cbc|abcCbc|abc ; ;【解解】删除删除无用产生式无用产生式：自定己自定己；不终结不终结；不可达不可达。 找找自定己自定己产生式产生式 （如（如 A - AA - A） 无无自定己自定己者！者！ 构造构造可终结非终结符集可终结非终结符集 V Vvtvt= , = , 构造构造可达非终结符集可达非终结符集 V VARAR= , = , G(S): S-G(S): S-aSab|bABaSab|bAB ; A- ; A-bB|abB|a ; B- ; B-aA|b
26、aA|b删除删除不可达不可达非终结符非终结符：C,D C,D 后后 得：得：无无不终结不终结者！者！A A ,B,B ,C,C ,D,D ,S,SS ,A ,BS ,A ,B谢谢收看！谢谢收看！正规式描述语言的简单运算例：正规式描述语言的简单运算例：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.
27、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* = =. .
