编译原理--有限自动机

第三章有穷自动机•要点：1.DFA和NFA的定义2.NFA→DFA的转换；3.DFA的化简4.正规文法、正规式、有穷自动机之间的相互转换；编译原理2有穷自动机有穷自动机（或有限自动机）作为一种识别工具，它能正确地识别正规集，即识别正规文法所定义的语言和正规式所表示的集合。引入有穷自动机这个理论，正是为词法分析程序的自动构造寻找特殊的方法和工具。分类：确定的有穷自动机（DFA）不确定的有穷自动机（NFA）33.1概述有穷自动机（FA）有穷自动机（FA，FiniteAutomata）是一种有限离散数字系统的抽象数学模型。这个系统具有有限数目的内部“状态”。所谓状态，是可以将事物区分开的一种标识。例如：数字电路（0，1），十字路口的红绿灯等都是离散状态系统，其状态数目是有限的。连续状态系统则如水库的水位、室内温度变化等。电梯的控制机制，不需要保存所有以前的服务要求，仅需记住当前的层次、运动的方向以及未满足的服务要求。文本编辑程序和词法分析程序是有限状态系统，计算机本身和人的大脑也可看成有限状态系统。4例过河问题题目一个人带着一头狼、一头羊以及一棵青菜，处于河的左岸，需要渡到河的右岸。有一条小船，每次只能携带人和其余的三者之一。不能让狼和羊单独在一起，无论在左岸还是右岸，否则狼会吃掉羊。同样，也不能让羊和青菜单独一起。如何才能安全渡过河呢？5例过河问题分析观察每次摆渡后河两岸的局势，使问题模型化。人（M），狼（W），羊（G），菜（C）。存在有16种子集，用连字号”-”连接子集的对偶表示状态，例如：MG-WC，表示：人和羊在左岸，狼和菜在右岸。16种状态中的某些状态，是不应该引入系统的，例如GC-MW，有关死活。人所进行的摆渡活动，可作为系统的输入。人可单独过河（输入为M），带着狼过河（输入为W），带着羊过河（输入为G）或者是带着菜过河（输入为C）。问题：初始状态应该是什么？终止状态应该是什么？6例过河问题分析（续）初始状态：MWGC-φ；终止状态：φ-MWGC。MWGC-φWC-MGg问题：7例过河问题状态转换图MWGC-φWC-MGC-MWGMWG-CMGC-WG-MWCMG-WCφ-MWGCW-MGCMWC-Gggggmggggmmmcccc有穷自动机（FA）数字系统：可以从一个状态移动到另一个状态；每次状态转换，都上由当前状态及一组输入符号确定的；可以输出某些离散的值集。FA：一个状态集合；状态间的转换规则；通过读头来扫描的一个输入符号串。读头：从左到右扫描符号串。移动（扫描）是由状态转换规则来决定的。9ddd;.dd+;输入符号串一个FA的例子读头数字A数字+-.SGBH数字数字..数字接收：若扫描完输入串，且在一个终止状态上结束。阻塞：若扫描结束但未停止在终止状态上；或者为能扫描完输入串（如遇不合法符号）。不完全描述：某些状态对于某些输入符号不存在转换。练习：+34.567.1233.4.510=80;0134256eniL字母字母字母字母数字数字数字==；；0124563Line=80;id,‘Line’=,num,‘80’;,数字数字字母字母11==0003;;1输入符号串输出有限控制器读头113.2有穷自动机的形式定义DFA:DeterministicFiniteAutomataNFA:NondeterministicFiniteAutomataDFA的定义定义3.1一个确定的有穷自动机(DFA)M是一个五元组：M=(K,Σ,f,S,Z)(1)K是一个非空有穷集合，它的每一个元素称为一个状态；(2)Σ是一个有穷字母表，它的每一个元素称为一个输入字符；Σ也称为输入符号字母表12确定的有穷自动机DFA的定义（续）(3)f是从Σ×K到K的单值部分映射；f(ki,a)=kj，其中ki∈K，kj∈K说明：当前状态为ki，输入字符a时，将转换到下一个状态kj，把kj称为ki的一个后继状态。DFA的确定性就表现在f是单值函数，即对任意状态k∈K，输入符号a∈Σ，f(k,a)唯一确定一个状态。(4)S∈K，是唯一的初态；(5)Z是K的子集，是一个终态集，终态也称为可接收状态或结束状态。13确定的有穷自动机DFA的表示3.2.1状态转换图设DFA有m个状态，n个输入字符，那么这个图含有m个状态结，每个结点最多有n条箭弧射出和别的结点相连接，每条弧用Σ中的一个不同输入符号作记号。整个图含有唯一的一个初态和若干个（可以0个）终态结。习惯上，初态结可以用“=”或“－”表示，终态结用双圆圈表示或标以“+”。对f(ki,a)=kj指从状态结ki到状态结kj画标记a的弧。14例１题：DFAM=({0,1,2,3}，{a,b}，f，0，{3})，其中f定义为：f(0,a)=1，f(0,b)=2，f(1,a)=3，f(1,b)=2，f(2,a)=1，f(2,b)=3，f(3,a)=3，f(3,b)=3解：该DFAM的状态图：0123abbaaba,b15确定的有穷自动机DFA的表示（续）3.2.2状态转换矩阵矩阵的行表示状态，列表示输入字符，矩阵元素表示相应的状态行在输入字符列下的新的状态，即f(k,a)的值。16例２（题同１）解：该DFAM的矩阵表示状态字符ab0121322133330123abbaaba,b0001173.2.3有关自动机术语(1)道路：对于Σ*中的任何字α，若存在一条从初态到某终态的路径。(2)识别：道路上所有弧的标记连接成的字等于α，则称α可为DFAM所识别（所接受）。即若t∈Σ*,f(S,t)=P，其中S为DFAM的初始状态，P∈Z（终态集）。若M的初态结同时也是终态结，则空字ε可为M所识别，即Q∈K,f(Q,ε)=Q(3)运行：f(Q,t1t2)=f(f(Q,t1),t2)，其中Q∈K，t1t2为输入字符串，且t1∈Σ，t1t2∈Σ*18例３解：∵f(0,abba)=f(f(0,a),bba)=f(1,bba)=f(f(1,b),ba)=f(2,ba)=f(f(2,b),a)=f(3,a)=3∴得证题：试证abba可为例1的DFAM所识别（所接受）。0123abbaaba,b193.2.4有关确定有穷自动机的结论把DFAM所能接受的所有字（字的全体）记为L(M)。Σ上的一个字集V∈Σ*是正规的，当且仅当存在一个Σ上的确定有穷自动机M，使得L(M)=V。20有限自动机识别的语言例子例：下图中的自动机所能识别的语言是什么？q0q2q1q3abbaba21定义3.4一个不确定的有穷自动机NFAN也是一个五元组：M=(K,Σ,f,S,Z)(1)K是一个有穷集合，它的每一个元素称为一个状态；(2)Σ是一个有穷字母表，它的每一个元素称为一个输入字符；Σ也称为输入符号字母表(3)f是一个K×Σ*到K的子集的映射：f:K×Σ*→2k(4)S是K的子集，是非空的初态集；(5)Z是K的子集，是一个终态集，也称可接收状态或结束状态。3.2.5不确定的有穷自动机(NFA)的定义22NFA的表示用状态转换图（∵f是多值函数）由NFA的定义，可把一个含有m个状态和n个输入字符的NFA表示如下：图中有m个状态结，对每个状态结可射出若干条弧和别的状态结相连，且每条弧用Σ*中的一个字（不一定要不同的字且可以是空字ε）作标记（或称输入字）。整个图中至少含有一个初态结以及若干个（可以是0个）终态结。某些结既可以是初态结也可以是终态结。23例４题：一个NFAM＝({s,t}，{0,1}，f，s，{t})，其中f(s,0)={s,t},f(s,1)={t},f(t,0)=Φ,f(t,1)={s,t},解：其状态图如下：s0t011124例５0a,b1aabba,b2a,b如下状态图也是一个NFAε25有关非确定有穷自动机的术语对于Σ*中的任何一个串t可被NFAM识别是指：若对这个字（串）t存在一条从某个初态结到某一个终态结的道路，且这条道路上所有弧的标记字依序连接起来的字（不理睬那些标记为ε的弧）等于t，则t可识别（或可接受）若M的某些结点既是初态结也是终态结，或存在一条从某个初态结到某个终态结的ε道路，则空字ε可为M所识别（所接受）。26补充：递归思想构造文法在某些复杂的语言中，字符串可能包含一种结构，它递归地作为另一种（或者同一种）结构的一部分而出现，可利用递归思想来构造对应的文法。例1：定义语言L={ω|ω中a和b的个数相同}的文法。解：先构造出基础情况的文法：S-ab|ba|ε再递归地构造出归纳情况的文法（新的生成式不能改变a和b的个数关系）：S-Sab|aSb|abS|Sba|bSa|baS27递归思想构造文法（续）例1：求一个文法G，使得Ｌ(G)即该文法的语言是奇数个ａ和奇数个ｂ的组合。解：因为语言是奇数个ａ和奇数个ｂ的组合，所以打头的最小语言有四种组合：aabbabba定义S和A，S是表示奇数个a和奇数个b的组合，而A是表示偶数个a和偶数个b的组合。开始递归构造文法：S-aaS|bbS|abA|baA……A-aaA|bbA|abS|baS|ε……28补充：如何设计有限自动机如同文法的设计，自动机的设计也是一个创造过程。有一种做法，在设计各种类型的自动机时都很有帮助，即采用一种心理上的技巧，把自己放在要设计的机器的位置上，考虑自己该如何实现自动机的任务。假定自己是一台有限自动机，接受到一个输入符号串时，必须确定到目前为止所看到的字符串是否可为该自动机所识别。为了能够判断这一点，必须估算出识别时需要记住哪些关键的东西。为什么不记住所有看到的东西呢？因为你是一台有限自动机，只有有限个状态，而这些状态是你记住事情的唯一办法。输入串可能很长，而你不可能记住所有的事情。幸运的是，许多语言只需要记住某些关键的信息就可以了。29设计有限自动机（续）例1：构造一台有限自动机，识别所有由奇数个a和奇数个b组成的字符串。解：为了确定a和b的个数是否是奇数，不需要记住所看到的整个字符串，而只需要记住至此所看到的a、b个数是偶数还是奇数即可。一旦确定了关键信息，就可以开始设计状态了。这些信息有如下四种可能性：30设计有限自动机（续）例1：(1)到此为止是偶数个a和偶数个b;(2)到此为止是奇数个a和偶数个b;(3)到此为止是偶数个a和奇数个b;(4)到此为止是奇数个a和奇数个b。根据每种可能性设计一个状态，并根据可能的输入符号来设计状态之间的转移条件。1324aaaabbbb31设计有限自动机（续）例2：设计有限自动机M，识别含有00作为子串的所有{0，1|*上的字符串组成的语言。如：0010，1001，110001001解：3种可能性：(1)到此为止未看到模式“00”的任何符号;(2)到此为止看见了一个0;(3)到此为止已经看见整个模式“00”。32设计有限自动机（续）例2自动机的状态转换图为：qq0q0010,1100或者为（NFA）：qq0q000,10,10033NFA和DFA的关系DFA是NFA的一个特例。•对于每个NFAM，存在一个DFAM’，使得L(M)=L(M’)•对于任何两个有穷自动机M和M’，如L(M)=L(M’)则称M和M’是等价的。•如果M仅通过重新标记它的状态，就能转换成M’，则M和M’称为同构的。•对于每一个FAM，存在一个等价的、具有最少状态个数的FAM’，对于其它的FAM’’，若M’’的状态个数与M’相同且等价与M’，则必然有M’’与M’同构，即：M’在结构上是唯一的。343.3NFA→DFA的转换（NFA的确定化）通过以下步骤，可以将一个NFA转换为等价的DFA：1.寻找并消除空移环路；2.消除余下的空移；3.确定化。353.3.1NFA中空移环路的寻找和消除空移环路：一个空移环路，是一个从状态A开始，并以状态A结束的空移动序列。εq1q2εq1q2εq3εq1q2εq3εqnε……ε消除方法：合并环路上的结点为新结点。若含初态，则新结点为初态。若含终态，则新结点为终态。363.3.2NFA的消除空移εABa1q1q2qna2an…εABa1q1q2qna2an…a1a