《计算机数学基础第二章.》由会员分享，可在线阅读，更多相关《计算机数学基础第二章.（30页珍藏版）》请在金锄头文库上搜索。
1、第二章有限自动机Date1计算机科学的数学基础2.1有限自动机的定义与构造有限自动机（FiniteAutomataFA）或称为有穷状态的机器，由一个有限的内部状态集和一组控制规则组成。在计算机科学中，可以找到许多有限状态系统的例子，如计算机本身也可以是认为是一个有限状态系统。有限自动机与正规文法和正规式有着非常密切的关系，它们的描述能力是相同的。Date2计算机科学的数学基础例2.1构造一个有限自动机M0，它能识别出除以3余2的二进制数。解：用V3(x)来表示二进制数x除以3的余数，例如，V3(100)1V3(1011)2，设输入符号串为wa1a2an，其中ai01，0in。显然，对于每一个i
2、，0in，自动机读入符号串a1a2ai后，二进制数a1a2ai除以3的余数V3(a1a2ai)必然为0、1、2之一，不可能有其它情况。因此可知，在自动机M0中只需要采用三个状态来分别表示上述的三种情况即可。令自动机M0中有状态q0、状态q1和状态q2分别表示余数为0、1和2的情况。Date3计算机科学的数学基础状态之间的转换当M0读完符号串a1a2ai后又读到符号ai+1时，新符号串a1a2aiai+1除3的余数与原符号串a1a2ai除3的余数之间显然有：V3(a1a2aiai+1)2V3(a1a2ai)+ai+1(mod3)101010图2.1有限自动机M0q0q1q2Date4计算机科学的
3、数学基础自动机的抽象模型可以将有限自动机抽象地描述成如图2.2所示的模型，该模型由一条无穷长度的输入带、一个读头和一个有限控制器组成。图2.2有限自动机读头有限状态控制器010110输入带Date5计算机科学的数学基础确定的有限自动机定义2.1一个确定有限自动机(DFA)M是一个五元组M=(Sfs0Z)其中：是有穷字母表它的每一个元素称为一个输入符号；S是有限状态集，它的每一个元素称为一个状态；f是转换函数，是从SS上的一个单值映射，即f(pa)q，q称为p的后继状态；s0S是一个唯一的初始状态；ZS是一个终止状态集。对于一个给定的属于该自动机的状态和一个属于该自动机字母表的字符，它都能根据事
4、先给定的转移函数转移到下一个唯一确定的状态（这个状态可能是先前那个状态）。定义2.2DFAM所接受的符号串的集合称为DFAM所接受的语言，记为L(M)，即：L(M)w|f(s0w)Z，wDate6计算机科学的数学基础不确定的有限自动机(NFA)定义2.3一个不确定有限自动机M是一个五元组M(SfS0Z)其中：是有穷字母表每一个元素称为一个输入符号；S是有限状态集，每一个元素称为一个状态；f是转换函数:S(S)上的映射(S)是S的幂集)，即f(pa)q1.qk，表示当前的状态为p，输入符号为a时，则转换到的状态是一个状态集；S0S是初始状态集；ZS是终止状态集。对于一个给定的属于该自动机的状态和
5、一个属于该自动机字母表的字符，它将根据事先给定的转移函数转移到下一个不确定的状态（因为转换到的状态是一个状态集）。Date7计算机科学的数学基础DFA与NFA的比较DFA的转换函数是从S到S上的一个单值映射。NFA的转换函数是从S到(S)(S的幂集)的映射，而不是到S的映射，即一个状态可转换到的后继状态是一个状态集合(可能是空集)，而不是单个状态。NFA有一个初态集DFA的初态是唯一的。DFA和NFA都正好识别正规集。它们之间存在着时空权衡问题DFA识别速度快，占用空间大，NFA识别速度慢，占用空间小。Date8计算机科学的数学基础非确定有限自动机的推广将具有动作的非确定有限自动机定义为五元组
6、(SfS0Z)，其中除转移函数f外的分量的定义如同定义2.3，但转移函数f是如下映射：S()(S)f(q)q。若NFA的某些状态既是初态又是终态，则空字可为该NFAM所接受。具有动作的NFA并不增加NFA接受语言的能力。Date9计算机科学的数学基础定理2.1对任何一个具有动作的NFAM，一定存在一个不具有-转移的NFAM，使得L(M)L(M)。其证明的基本思想是去掉弧。DFA可视为NFA的一个特例，其中：(1)没有一个状态有转换；(2)对每一个状态s和输入符号a，最多只有一条标记为a的弧离开。对于任何两个有限自动机M和M，如果L(M)L(M)，则称M和M是等价的。Date10计算机科学的数学
7、基础2.4NFA的确定化如果把状态子集看作是整体，即把一个状态子集看作是一个（扩展）状态，那么NFA的不确定性就不存在了（子集构造法）。定理2.2设L(M)为一个由NFAM接受的集合，则存在一个接受L(M)的DFAM。图2.9与图2.5中NFA等价的DFAbabbbabaaa00，10，20，3ab013023将状态子集当作一个（扩展）状态看待Date11计算机科学的数学基础2.5DFA的最小化由于NFA的确定化算法中没有考虑到DFA中有些状态是等价的，故得到的DFA的状态数并不一定是最少的。定义2.6一个状态是DFAM的无用的如果从M的初态出发任何输入串都不能到达该状态.定义2.7DFAM的
8、两个状态s，t说是不可区别的，若对于输入字母表上的任何符号串w，DFAM分别从s和t开始，读完w之后，都同样终止于终态或者非终态。Date12计算机科学的数学基础终态与非终态是可区别的（令w=）。关系“不可区别”是一种等价关系。定义2.8如果两个状态是不可区别的，则称它们是等价的。定义2.9DFAM的状态最小化，是指构造一个等价的DFAM使得M是所有等价于M的DFA中状态数目最少的称M为最简DFA。DFAM是最简DFA，须满足如下两个条件：(1)没有多余状态；(2)它的所有状态都是可区别的，即没有两个状态是等价的。Date13计算机科学的数学基础DFA可表示为RE定理2.4：如果L被一个确定的
9、有限自动机接受，则L可以用一个正规表达式来表示。证明：令L被确定的有限自动机M所接受。设M=(q1q2qnq1F)。令Rikj表示所有这样的符号串x的集合，x满足条件(qix)=qj，并且对x的任何不同于x或的前缀y，若(qiy)=qs，则sk。注意到L(M)=qjFR1nj。若对任意ijk，Rikj均可表示为正规式，则L(M)亦可表示为正规式。Date14计算机科学的数学基础DFA可表示为RE递归地定义Rikj为：a|(qia)=qjija|(qia)=qji=jRi0j=Rikj=Rik1jRik1k(Rkk1k)Rkk1jqiqjqkRik1jRik1kRkk1kRkk1j归纳基础(k=
10、0)：显然Ri0j可表示正规式ri0j。假设对ijk，Rikj均可表示为正规式rikj，则Rik+1j亦可表示为正规式rik+1j，rik+1j=rikjrikk+1(rk+1kk+1)rk+1kj。由数学归纳法可知归纳假设成立。Date15计算机科学的数学基础双向有限自动机双向确定有限自动机（2DFA）是五元组M=(Q，q0，F)，其中Q，q0，F的定义和DFA一样，而是从Q到QL，R的映射。若(q，a)=(p，L)，则2DFA在状态q扫描输入符a后进入状态p并将磁头左移一个单元。若(q，a)=(p，R)，则2DFA进入状态p并将磁头右移一个单元。Date16计算机科学的数学基础2DFA的瞬
11、时描述M的一个瞬时描述是Q中的一个符号串，瞬时描述wqx，其中w和x属于，而q属于Q，表示了如下的事实：1、wx为输入符号串；2、q是目前的状态；3、输入磁头正在扫描x的第一个符号。如果x=，则输入磁头已经离开了输入符号串的右端。Date17计算机科学的数学基础2DFA的瞬时描述的演变定义关系M，或（当M是已知时），为：（1）a1a2ai1qaiana1a2ai1aipai+1an，当(qai)=(pR)，和（2）a1a2ai2ai1qaiana1a2ai2pai1aian，当(qai)=(pL)，并且i1。(2)中条件i1防止使磁头从磁带左端移出的动作。注意，当i=n+1时不可有任何移动（因
12、磁头已移出右端）。令为的自反闭包，即有II；或I2，Ik-1，使得I1I2Ik，则I1Ik。Date18计算机科学的数学基础2DFA及其瞬时演变右图是一个2DFA。q01010011q10100110q110011q20100110q01001101q10011010q10110100q111010q20110100q01101001q101q0(q0R)(q1R)q1(q1R)(q2L)q2(q0R)(q2L)状态输入2DFAM101001q0q1q1q2q0q1q1q1q2q0q1左表中2DFAM动作的图示下表是其阅读输入101001的演变：Date19计算机科学的数学基础将2DFA看成单
13、向运动如果我们把2DFA在每两个单元之间的边界下反复通过的状态看作一个整体，不妨把这些通过的状态序列称为通过序列。101001从通过序列看2DFA的运动q0q1q1q2q0q1q1q1q2q0q1从通过序列的角度看，则是从前一个通过序列到达后一个通过序列的单向运动。Date20计算机科学的数学基础2DFADFA的两个问题将2DFA转换为单向运动需要解决两个问题：首先，能否用有限的状态来模拟通过序列。其次，怎样来确定通过序列之间的转换。Date21计算机科学的数学基础有效通过序列是有限的只需考虑被2DFAM所接受的符号串的通过序列，称之为有效通过序列。有效通过序列是有限的。因为：1、若M接受该输
14、入串，则其通过序列在磁头移动的同方向上不能有重复状态，否则，M因其确定性而将陷入循环而永远不会移出输入带右端。设M有n个状态，则有效通过序列长度不能超过2n。2、磁头首次通过该边界时必是向右，随后的通过必是与前次反向，末次通过必是向右。故有效通过序列的长度都为奇数2n1。Date22计算机科学的数学基础有效通过序列之间的转换设含符号a的单元的左、右边界的通过序列q=q1q2qk和p=p1p2pl是相容的。aq1q2qkp1p2pl若M是向右移动进入通过序列q和p，即(q1a)=(p1R)，则称q右匹配p。若M是向左移动进入通过序列p和q，即(p1a)=(q1L)，则称q左匹配p。aq1q2qk
15、p1p2plDate23计算机科学的数学基础有效通过序列之间转换的构造(a)、若q3qk右匹配p1pl，且(q1a)=(q2L)，则q1q2q3qk右匹配p1pl。(b)、若q2qk左匹配p2pl，且(q1a)=(p1R)，则q1q2qk右匹配p1p2pl。q3qkq1q2ap1pl(a)：q1p1(b)：ap2plq2qkDate24计算机科学的数学基础有效通过序列之间转换的构造(c)、若q1qk左匹配p3pl，且(p1a)=(p2R)，则q1q2q3qk左匹配p1pl。(d)、若q2qk右匹配p2pl，且(p1a)=(q1L)，则q1q2qk左匹配p1p2pl。q1qkp1p2ap3pl(c)：q1p1(d)：ap2plq2qkDate25计算机科学的数学基础2DFA接受的仍然是正规集定理2.5：如果L被一双向确定有限自动机接受，则L是一正规集。证明：设M=(Qq0F)为2DFA。现构造一个NFAM=(Qq0F)，其中(1)Q由M的所有有效通过序列组成；(2)q0是只由q0构成的通过序列；(3
