第二章有限自动机和正规文法2.1确定的有限自动机(DFA)(DeterminateFiniteAutomaton)有限自动机是研究自动系统的一种数学模型,它出现于本世纪四十年代。1943年由McCulloch与Pitts建立了模拟神经网络的自动机,1956年由Moore建立了描述计算机的时序机的概念。以后自动机的理论日趋发展,并且与计算机的信息处理密切结合,它不仅用于研究计算机的结构,还用于研究形式语言——语言的识别。在这里主要是从识别语言这方面来研究自动机。一.有限自动机(FA)的结构有限自动机由三部分构成:1.输入带输入带可以任意长,带上有若干单元,每个单元内有输入符号。输入带上存放的是被有限自动机识别的符号串。如图所示,输入带上的符号串为:a1a2a3…an。2.读头读头是将输入带上的符号读到有限控制器中,每次读一个单元的符号。有限控制器a1a2a3…an输入带读头3.有限控制器有限控制器是有限自动机的核心。有限自动机有多个状态,有一个开始状态,还有若干个终止状态。自动机每读带上一个符号,状态可能发生变化,然后读头右移一个单元。自动机如何从开始状态出发,识别完带上的整个符号串后,要进入某个终止状态,这个过程就是由有限控制器控制的。二.确定的有限自动机(DFA)的形式描述定义:确定的有限自动机M写成有序五元组,记作M=(K,∑,δ,q0,F)其中,K——有限自动机的状态的有限集合。∑——输入带上的有穷字母表。δ——状态转移函数,是K×∑→K的映射。例如,δ(q,a)=p(其中q,p∈K,a∈∑),表示在q状态下,读a后,状态改为p,然后,将读头右移一个单元。q0——开始状态q0∈KF——终止状态集合,FK三.确定的有限自动机的表示方法【例2-1.1】给定确定的有限自动机M=(K,∑,δ,q0,F)K={q0,q1,q2,q3},∑={0,1},F={q0}δ:δ(q0,0)=q2δ(q0,1)=q1δ(q1,0)=q3δ(q1,1)=q0δ(q2,0)=q0δ(q2,1)=q3δ(q3,0)=q1δ(q3,1)=q2状态转移函数δ也可以用函数表表示,如上表所示。01q0q2q1q1q3q0q2q0q3q3q1q2aqδ(q,a)=q(c)qqF(d)q0开始状态q0(a)qpδ(q,a)=p(b)a有限自动机还可以用图表示。方法如下:四.状态转移函数δ定义的扩充原δ:K×∑→K的映射。1100q0q1q2q3110001q0q2q1q1q3q0q2q0q3q3q1q2ˆ(q,ε)=qM的状态转移图:为描述有限自动机M接收的语言,将δ函数扩充成:ˆ:K×∑*→K的映射。对于任何x∈∑*,如果ˆ一般地表示:ˆ(q,x)=p,表示在状态q下,读符号串x后,到状态p。ˆ(q,xa)=δ((q,x),a)其中x∈∑*,a∈∑ˆ例如上例中(q0,010)=δ((q0,01),0)=δ(δ((q0,0),1),0)ˆˆˆ=δ(δ(q2,1),0)=δ(q3,0)=q1。ˆ=δ(δ(δ((q0,ε),0),1),0)=δ(δ(δ(q0,0),1),0)ˆ但此时的δ一定理解成。ˆ(q0,010)=q1也可以写成δ(q0,010)=q1。造成混淆,所以ˆ起见,符号δ与可以不作区分地使用,这样做也不会可见在确定的有限自动机中,是由δ定义的,为了简单ˆ五.确定的有限自动机M接收的语言T(M)给定确定的有限自动机M=(K,∑,δ,q0,F),M接收的语言T(M)为:T(M)={w|w∈∑*且δ(q0,w)=p其中p∈F}例2-1.1中,T(M)=?1100q0q1q2q31100T(M)={w|w∈{0,1}*且w中有偶数个0或者偶数个1}。•作业题1.设计一个有限自动机(FA)M,使得T(M)中的每个句子w同时满足下面三个条件:1)w∈{a,b,}*;2)|w|是3的整数倍;3)w以a开头,以b结尾。2.设计二个FAM1和M2,分别满足T(M1)={02i∣i是自然数}T(M2)={02i+1∣i=0,1,2,3,4,…}2.2不确定的有限自动机(NFA)(Non-deterministicFiniteAutomaton)DFA是在每个状态下,读一个符号后的下一个状态是唯一确定的,下面讨论的有限自动机是在某个状态下,读一个符号后的下一个状态可能不是唯一确定的,这就是不确定的有限自动机。一.不确定的有限自动机(NFA)的形式定义定义:不确定的有限自动机M,用一个有序五元组表示:M=(K,∑,δ,q0,F)其中,K、∑、q0、F的含义同DFA。δ—状态转移函数,是K×∑→2K的映射。例.δ(q,a)={p,s}(其中q∈K,{p,s}∈2Ka∈∑)【例2-2.1】.给定NFAM,M=(K,∑,δ,q0,F)其中,K={q0,q1,q2,q3,q4}∑={0,1}F={q2,q4}δ:K×∑→2K为:01q0{q0,q3}{q0,q1}q1Φ{q2}q2{q2}{q2}q3{q4}Φq4{q4}{q4}q0q1q2q3q40,10,10,10011图2-2.1NFAM状态转移图二.状态转移函数δ定义的扩充原来δ:K×∑→2K,下面对它进行两次扩充。与确定的有穷自动机相类似,扩充以后的状态转移函数仍然用δ。因为这样做,在计算时也不会引起错误。1.将δ扩充成:δ:K×∑*→2K,定义为:x∈∑*,δ(q,x)={p1,p2,…,pn}({p1,p2,…,pn}∈2K)表示在状态q下,读符号串x后,可以达到状态pi(1≤i≤n)。一般地表示:δ(q,ε)={q}q∈K),(),(apxqpδ(q,xa)其中q∈K,x∈∑*,a∈∑δ(q0,01)=δ(q0,1)∪δ(q3,1)={q0,q1}∪Φ={q0,q1}例2-2.1中δ(q0,0)={q0,q3},则为了计算δ(q,xa)方便,2.将δ的定义再一次扩充成:δ:2K×∑→2K,对于任何P={p1,p2,…,pn}∈2K,a∈∑),(),(apxqp(2)δ(q,xa)=δ(δ(q,x),a)即δ(P,a)等于P中每个状态分别读a后状态集合的并集。δ的定义经过扩充之后,计算δ(q,xa)的式子可写成:δ(q,xa)=δ(δ(q,x),a)。于是对于任何x∈∑*,a∈∑(1)δ(q,ε)={q}q∈K),(apPpδ(P,a)=δ({p1,p2,…,pn},a)=三.NFAM所接收的语言T(M)给定NFAM=(K,∑,δ,q0,F),M所接收的语言T(M)为:T(M)={w|w∈∑*且δ(q0,w)∩F≠Φ}例2-2.1中,T(M)=?T(M)={w|w∈{0,1}*且w中或者有两个相邻的0或者有两个相邻的1}q0q1q2q3q40,10,10,10011图2-2.1NFAM状态转移图四.NFA转换成DFA任何一个NFA都可以等价地转换成DFA。定理2-2.1如果语言L可由一个NFAM所接收,则必存在一个DFAM’,使得T(M’)=L。证明:令NFAM=(K,∑,δ,q0,F),且T(M)=L。构造DFAM’=(K’,∑,δ’,q0’,F’),其中K’2K,K’中的元素是由K的子集{q1,q2,…,qi}构成,但是要把子集{q1,q2,…,qi}作为的一个状态看待,因此把此子集写成[q1,q2,…,qi]。q0’=[q0],F’={[q1,q2,…,qi]|[q1,q2,…,qi]∈K’且{q1,q2,…,qi}∩F≠Φ}δ’:K’×∑→K’,对[q1,q2,…,qi]∈K’,a∈∑,有δ’([q1,q2,…,qi],a)=[p1,p2,…,pj]当且仅当δ({q1,q2,…,qi},a)={p1,p2,…,pj}这说明:计算δ’时,完全取决于NFA中δ(注:为了更好地理解如何根据NFAM构造DFAM’,可以先看例子,然后再看下面的证明,这样更容易理解证明的过程。)例.将例2-2.1中的NFAM等价变换成DFAM’。按照上述定理给定的方法。令M’=(K’,∑,δ’,q0’,F’),其中,K’、F’:因为K’2K,在求K’时,不需要将2K中的所有元素都列入K’,只需要列入从开始状态[q0]可以达到的状态即可,为此可以先求δ’,然后得到K’和F’。例2-2.1:NFAM=(K,∑,δ,q0,F)其中,K={q0,q1,q2,q3,q4}∑={0,1}F={q2,q4}构造DFAM’=(K’,∑,δ’,q0’,F’),q0’=[q0]δ’:[q1,q2,…,qi]∈K’,a∈∑,有δ’([p1,p2,…,pj],a)=[q1,q2,…,qn]当且仅当δ({p1,p2,…,pj},a)={q1,q2,…,qn}从[q0]开始,计算各个可达状态的转移函数。例如要计算δ’([q0,q3],0)首先计算δ({q0,q3},0)。δ({q0,q3},0)=δ({q0},0)∪δ({q3},0)={q0,q3}∪{q4}={q0,q3,q4},于是δ’([q0,q3],0)=[q0,q3,q4],其余的依此类推。最后得下表01q0{q0,q3}{q0,q1}q1Φ{q2}q2{q2}{q2}q3{q4}Φq4{q4}{q4}δ:K’={[q0],[q0,q3],[q0,q1],[q0,q3,q4],[q0,q1,q2],[q0,q2,q3],[q0,q1,q4],[q0,q2,q3,q4],[q0,q1,q2,q4],}F’={[q0,q3,q4],[q0,q1,q2],[q0,q2,q3],[q0,q1,q4],[q0,q2,q3,q4],[q0,q1,q2,q4]}01[q0][q0,q3][q0,q1][q0,q3][q0,q3,q4][q0,q1][q0,q1][q0,q3][q0,q1,q2][q0,q3,q4][q0,q3,q4][q0,q1,q4][q0,q1,q2][q0,q2,q3][q0,q1,q2][q0,q2,q3][q0,q2,q3,q4][q0,q1,q2][q0,q1,q4][q0,q3,q4][q0,q1,q2,q4][q0,q2,q3,q4][q0,q2,q3,q4][q0,q1,q2,q4][q0,q1,q2,q4][q0,q2,q3,q4][q0,q1,q2,q4]δ’:01q0{q0,q3}{q0,q1}q1Φ{q2}q2{q2}{q2}q3{q4}Φq4{q4}{q4}δ:M’的图:[q0][q0,q1]111111111000000000[q0,q1,q2][q0,q3,q4][q0,q2,q3][q0,q1,q4][q0,q2,q3,q4][q0,q1,q2,q4]图2-2.2M’的状态转移图[q0,q3]证明:T(M’)=T(M)1.先用归纳法证明(对输入符号串|x|归纳)下面命题成立:对于任何x∈∑*,δ’(q0’x)=[q1,q2,…,qn]当且仅当δ(q0,x)={q1,q2,…,qn}(1)当|x|=0,即x=ε时,δ’(q0’,ε)=q0’=[q0]当且仅当δ(q0,ε)={q0},命题成立。(2)假设|x|≤k时,命题成立。即δ’(q0’,x)=[p1,p2,…,pj]当且仅当δ(q0,x)={p1,p2,…,pj}(3)当|xa|=k+1时,a∈∑,有δ’(q0’,xa)=δ’(δ’(q0’,x),a)δ(q0,xa)=δ(δ(q0,x),a)因为|x|=k,由假设(2)得δ’(q0’,x)=[p1,p2,…,pj]当且仅当δ(q0,x)={p1,p2,…,pj}。故δ’(q0’,xa)=δ’([p1,p2,…,pj],a)当且仅当δ(q0,xa)=δ({p1,p2,…,pj},a),所以命题成立。2.再证明T(M’)=T(M)对于任何x∈∑*,如果x∈T(M’),则δ’(q0’,x)∈F’,令δ’(q0’,x)=[p1,p2,…,pj],即[p1,p2,…,pj]∈F’。因命题δ’(q0’,x)=[p1,p2,…,pj]当且仅当δ(q0,x)={p1,p2,…,pj}成立
本文标题:计算理论基础章2
链接地址:https://www.777doc.com/doc-1654126 .html