理论计算机复习整理

1. 形式化2形式语言3数理逻辑：4理论计算机科学理论计算机科学是关于计算、算法、程序和计算机的数学理论。有许多分支，包括计算理论、.形式语言 理论、形式语义理论，等等。2将下列NFA转化为等价的DFA。解：用状态子集法构造DFA的转移矩阵如下。输入符状态 、ab00, 100,10, 11,2* 1,201, 2000用整数代码表示状态，将转移矩阵改写如下:输入符状态、ab124223* 343444据此画出状态转移图如下:1.正规表达式转化为带空转移的NFA定义2.1我们用正规表达式标记有限自动机中的转移，表示该转移可以处理该正规表达式所表示的任何 输入串，这种有限自动机称为广义有限自动机，简称GFA。GFA拆分法：将正规表达式转化为等价的-NFA。wlv2. 将有限自动机转化为正规表达式GFA去状态法第1步去掉陷阱状态。第2步添加两端状态。在自动机转移图的两端添加一个新的开始状态X和一个新的接受状态Y，让X 空转移到原来的开始状态，并且让原来所有接受状态空转移到Y。第3步 合并转移。合并两个状态之间的所有方向相同的转移为一个转移，其标记为所有被合并的转移上 的标记的并。如下图所示。第4步 挖去内部状态。去掉一个内部状态，将该状态的每个入转移与每个出转移分别连接为一个转移。 m个入转移与n个出转移相互连接后形成mn个新转移。设一对入转移和出转移上所标记的正规表达式 分别为w和v，则连接后新转移上的标记如下定义：若被去掉的状态上没有指向自己的转移，该标记为 wv；若被去掉的状态上有一个标记为r的环，则该标记为wr*v。如下图所示。v第5步 重复第3步和第4步，直到只剩下状态X到和Y以及二者间的一条转移，则该转移上的正规表达 式就是所要求的结果。3. 将带空转移NFA转化为DFA的方法定义4.1(空转移闭包或e-闭包)对于带空转移的NFA来说，其某个状态q的空转移闭包，记为s-Closure(q)， 是由该状态自身，以及该NFA从此状态出发，经过若干次空转移后，所能到达的所有状态构成的集合。根据定义不难计算空转移闭包。我们可以在状态转移图上，跟踪空转移，标记出所有空转移所到达的状 态，然后将这些被标记的状态一一添加到所要求的闭包中即可。状态子集闭包法将s-NFA转化为等价DFA，按如下3步构造该DFA的转移矩阵。第1步，算出s-NFA的开始状态的s-闭包，作为DFA的开始状态。第2步，为每个DFA状态构造后继状态。令R为DFA的一个状态，a是一个输入符号。我们构造R的 a-转移后继状态S如下。S = s -Closure( q | 3p e R.q e 8 (p,a)即，若R某状态p经过a转移可到达状态q，则将q添加到S中，当没有状态可以添加时，再对S求空转 移闭包。此时所得的S就是R的a一转移后继状态。第3步，将含NFA接受状态的DFA状态都指定为接受状态。第6讲米希尔-奈罗德定理与DFA最小化一个正规语言的DFA是无穷多的，其中状态数最小的称为最小DFA。在实际应用中，作为一种算法， DFA当然是越小越好。本讲讨论如何将一个DFA等价变换为最小DFA。这个等价变换的理论基础是米 希尔-奈罗德定理。3. 等价类：相互等价的所有元素构成的集合称为一个等价类。元素x所在的等价类记为x。注意，x与y要么相等要么不相交。n4. 集合的划分:设Al M序是A的一组子集。若A.互不相交且A =A，则称A 11 V I V nIIII是A的一个划分(partition)。命题1.设R是A上的一个等价关系，则R的所有等价类构成A的一个划分。命题2.设n是集合A的一个划分。定义A上二元关系Rn如下：xRny当且仅当存在A. 6口, x, y E A.则Rn是等价关系。推论3. 一个集合上的等价关系与该集合的划分是一一对应的。1. 字符串集合上的两个等价关系我们先回顾一个定义，即有限自动机的状态所接受的语言。设M是一个有限自动机，q是其状态。 若M从开始状态出发处理完串x后恰好到达状态q，则称q接受x。q接受的所有串构成q所接受的语言， 记为L(q)。若M是DFA，则M可以确定地处理完任何串并且到达某个唯一状态，所以M的不同状态所接 受的语言是不相交的。因此，DFA各状态所接受的语言构成了输入串集合的划分。这个划分定义了一个等 价关系：若两个输入串被DFA的同一个状态所接受，则称这两个串在该有限自动机下是等价的。x定义1.2设M是一个DFA，其输入符号表为。我们在输入串集合*上定义二元关系Rm如下RM=(x, y )x, y被M的同一个状态所接受显然Rm是*上的等价关系，称之为M中的等价关系(equivalence inM)。定义1.3设L是一个语言，其符号表为乙 我们在Z*上定义二元关系Rl如下，%=(*，y)l(Vz)xz e L o yz e L读者不难验证Rl是z*上的等价关系，我们称之为关于L的等价关系(equivalence toward L)。也许更文 艺点，可称之为“走向L的等价关系”。我们可以这样来理解该等价关系。令x为一个串，则任何串z作为后缀连接到x上只能导致两个结 果，即要么xz在L中要么xz不在L中。前者将x带到了 L中，后者将x带到了 L外。反过来，我们看 到所有串z被x划分为两类，即z eZ * | xz e L和z eZ * | xz冬L。前者可以视为x的正确向导集，后者为x的错误向导集。因此，当且仅当两个串的正确向导集相同时才是关于L等价的。引理1.4设L是正规语言，M是接受L的DFA，则Rm Q R，从而L的等价类数小于等于M的状态 数。证明：设L的字母表为Z，以下所讨论的串都是该字母表上的串。设(x, y) e Rm，则对任何zeZ*,有 (xz, yz) e Rm，从而有xzeL o yzeL，即(x, y) e Rl .这证明Rm q Rl。对于任何串x，我们将 y在等价关系 r 和 r 下的等价类分别记为Y1 和y1 由于 R U R 我们有x U x因此x 1土寸I刀Rm 1-1 RlI口 J寸1刀 刀 力J心刀Xm甘Xl.由 于 m l，闩七心1-七。心 ML，Rm的等价类个数大于等于Rl的等价类个数。又由于Rm的等价类就是M各状态所接受的语言，从而与这 些状态是一一对应的，所以 Rm的等价类个数等于 M的状态数。这证明引理的第二个结论成立。 我们将用Rl的等价类作为状态构造一个接受L的最小DFA。2.米希尔-奈罗德定理定理2.1 (Myhill-Nerode) 正规语言L的最小DFA的状态个数恰好等于Rl的等价类个数。证明：1.构造最小DFA。根据上面的引理，Rl的等价类个数是有限的，我们用这些等价类作为有限自 动机的状态构造一个DFA如下：ML= (Q, Z, 5 , s, Q)其中状态集Q=*IRl，即Rl等价类集合，Z是L的符号表，开始状态$=目，Q/=(x I xeL，即L内的串的 等价类都是接受状态，L外的串的等价类都是非接受状态，对于任何状态x和符号a eZ， 5 (x, a)= xa ，即自动机在状态x下扫描字符a时就进入状态xa。2.论证Ml的正确性。我们对输入串的长度用归纳法，将证明对于任何输入串x eZ *，有X G L(x)由于目是ml的开始状态，所以8 G L(E)。假设对于任何长度不超过某个数的串X,都有x G L( x)。令a为任一输入符号。根据假设，ML在处理完x后进入状态x。根据ML的转移函数，Ml在状态x下处理字符a后进入状态xa，所以xa被状态xa所接受。这样我们就证明了断言(2.1.1)。 由此不难推出如下结论：对于任何输入串工，都有L(x)=x事实上，令yGx，则闰=列，从而yGL(x)，所以xwL(x)。下面证明L(x)wx。令七G L(x)。我们只需证明七G x。根据(2.1.1)，我们有七G L(七)。因此，z既被状态x所接受又 被状态z所接受。由于Ml是DFA，接受输入串的状态只能是唯一的，所以x=z。于是我们有z G x。这样我们就证明了 L(x) = x。由此可知，Ml接受的语言就是L。3.论证Ml的最小性。根据上面的引理1.4,立刻可知Ml是最小DFA。推论2.2如果不考虑状态名称上差异，则每个正规语言的最小DFA是唯一的。证明：设M是正规语言L的最小DFA。M只要更改各状态的名称就完全变为定理2.1证明中所构造的 Ml。由于M是L的最小DFA，根据Myhill-Nerode定理，M的状态个数=人乙的等价类个数。因此，RM的 等价类个数=*的等价类个数。根据上面的引理，rm w rl，从而rm =rl。由此可知，对于任何输 入串x，M中都有相应地存在唯一状态q恰好接受x的等价类，即L(q)=x。因此，M中各状态与其所 接受的等价类之间是一一对应的。我们将接受x的状态改名为集合x。注意，由于不同状态所接受的等 价类是不相交的，所以这个改名是可行的，即不会导致两个不同状态使用同一个名称。令a是任何输入 符号，则改名后的M在状态x下处理a后进入某个后继状态。由于该后继状态接受xa，所以该后继状 态所接受的等价类应当是xa，从而该状态为xa。由此可以看出，改名后的M完全变成了定理2.1证明 中所构造的ml。3. DFA的最小化方法首先，删除所有的无用状态，即从起始状态出发不能到达的状态。这样做并不改变原DFA的识别功能。其次，对DFA的状态集合进行分割。定义3.1设M是一个DFA。1)M的任何终止状态与非终止状态是可分离的。2)M的两个状态p与q是可分离的，当且仅当存在串w分别从这两个状态出发可以到达终态与非终态。引理3.2对于状态p和q，若存在字符a，使得状态5(p,a)与 5(q,a)是可分离的，则p与q是可分离的。p和q可分离r和s可分离.忑引理3.3对于状态p和q，若存在某个状态既与p不可分离又与q不可分离，则p和q是不可分离的。状态分割法：第1步，将终止状态与非终止状态相分离，得初步划分(Q-Qf，Qf)第2步，对当前划分中的每个子集做进一步的划分。方法如下：以当前所得的划分为标准，应用引理 3.2和3.3,确定当前子集中的所有可分离的状态对，据此划分该子集。重复第2步，直到没有可分离状 态对时为止。注：根据引理3.2不难看出，状态分割法是正确的，即对于任何DFA，根据该方法所构造的DFA是等价 的并且是最小的。例3.4给定NFAb,c图3.1用状态子集法得DFAbcb3.2现在我们需要最小化该DFA。解：该DFA的状态集记为Q=0,1,2,3,4,5首先将Q划分为拒绝状态集和接受状态集等两个部分。斗=0,1,2, 3,4,5其次，对当前划分中的集合继续尝试划分。%=0,1,2，3,4,5n3=0,1,2，3,4,5根据n3, 3,4,5中不存在可分离的状态对，所以n3就是最后所得的划分。最后，画出所得最小DFA如下。b,c4.用Myhill-Nerode定理证明非正规语言定理4.1(Myhill-Nerode)语言L是正规的当且仅当均的等价类个数是有限的。证明：若L是正规语言，则根据引理1.4, Rl有有限个等价类。反之，若Rl有有限个等价类，则根据 Rl，可以按照Myhill-Nerode定理2.1证明中的方法构造出接受L的有限自动机吟，所以L是正规语言。 例4.1用Myhill-Nerode定理证明L=anbn|n1不是正规语言。关键：找出无限个等价类。证明：设m n。注意到anbnL且ambn W L。根据电的定义可知，an与am不等价。因此，an和am是两个不相同的等价类。从而L有无限多个等价类。根据Myhill-Nerode定理，L不是正规语 言。练习4.2用Myhill-Nerode定理证明L=wwR|w(0|1)+不是正规语言。1. 正规语言类的封闭性根据本讲义的定义易知，正规语言类在并、连接和星闭包等正规运算下都是封闭的。定理1.1若A是正规语言，则Ac是正规语言。注：A的补集是相对于A的字母表上所有串而言的。证明设M是接受A的DFA。将M的接受状态改为非接受状态，将非接受状态改为接受状态，则所得 的DFA接受A的补集。事实上，由于M是DFA，所以对于语言A的字母表上任何串来说，M都有某个 状态接受该输入串。因此，M的所有非接受状态所接受的串构成A的补集。证毕思考：若M是接受语言A的NFA，则将M的接受状态改为非接受状态，将非接受状态改为接受状态， 所得的NFA接受A补吗？定义1.2 （乘积有限自动机）设M,N是两个具有相同输入符号表的DFA，则M和N的乘积有限自动机 MN定义如下：（1）若M和N的开始状态为0和0，则MN的开始状态为（0,0）；（2） 若（p,p）是MN的状态，则对于任何输入符号a，（p,p）的a-转移后继状态为（q,q）当且仅当p的a-转移后继状态为q且p的a-转移后继状态为q；（3）对于MN的任何状态（p,p），该状态是MN的接受状态当且仅当p和p分别是M和N的接受状态。例1.3令A为所有被2整除的二进制自然数，B为所有被3整除的二进制自然数。再令M，N是分别接 受A和B的DFA。试构造乘积有限自动机MN。定理1.7若A是正规语言，则AR也是正规语言。证明设M是接受A的DFA。由M构造接受AR的带空转移的NFA如下。（1）逆转所有转移的方向；（2）添加一个新的开始状态，空转移到所有的接受状态；（3）将M的开始状态指定为唯一的接受状，其中状态都是非接受状态。不能证明这个NFA恰好接受AR。证毕定理1.8若A，B是正规语言，则A/ B =z I存在 e A, y e B，使徐=yz是正规语言。证明 设M, N分别是接受A和B的两个DFA证毕2. 正规语言的泵引理定理2.1设L是正规语言，则存在一个常数奴对L中任何长度不小于k的串”，存在无yz，使得=工关 且1. xyi，3. Vz 0. xyiz e L.证明设M是接受L的DFA，有k个状态。设巧=% 七e L，其中n*。则M从开始状态处理 完w共经历n+1个状态，分别记为qo, %，勺畦。注意到n+1k+10因为M只有k个不同的状态，所 以在这n+i个状态中的前k+i个状态中一定有一个两个状态是相同的。令这两个状态为qr，qs其中 0rs0， 串 xyzz在M中可以先经过第1 段计算路径处理完x，然后用连续i次第2段路径处理y，最后用第3段路径处理z，最后停止在终止状 态q。因此，M接受xyzz，从而xyiz e L。注：泵引理中的常数k称为泵常数。例2.2令L=anbn|n1。用泵引理证明L不是正规语言。证明：用反证法。假设L是正规语言。则L有一个泵常数k。取w= akbk.根据泵引理，存在x，y，z使得w=xyz，其中|xy|1且xzL. 由|xy|1可知y 至少含一个a。因此xz中的a的个数小于k且b的个数等于k。由此可得xz不在L中。矛盾。口例2.3令L=aibj | i,j1,译j。用泵引理证明L不是正规语言。证明：假设L是正规语言。则L有一个泵常数k。取w = a+1)!.根据泵引理，存在x,y,z使得w=xyz,其中|句】砂Z E乙易知y中至少含一个 a且不含b,所以VZ中a的个数为k!+(i-1)n,其中Byl。令 k!+ (i - 1)n = (k +1)!(1)则i=空+1.n由于1n 1用归纳法不难证明上述结果是正确的。同理，由第3个方程可求得L(B) = vi I i 1再由第1个方程立刻可得L(S) = nivj I i, j 1这就是G1所生成的语言。顺便说一下，如果我们把文法G1中的终极符号n和v分别理解为名词和动词，则根据A的产生式， A可理解为由名词组成的名词短语，根据B的产生式，B可理解为由动词组成的动词短语，从而根据S 的产生式可知S所指代的语句是由名词短语连接动词短语所组成的。3.推导在乔姆斯基的文法理论中，把产生式用作推导规则(derivation rule)，可以开始符出发推出文法所生成a,或者a可代入A，所的任何句子。因此，我们把产生式A-a理解为A可推出a,或者A可重写为 以产生式也称为重写规则(rewrite rule)或者变元代入规则(subsituation rule)。定义2.1设G是上下文无关文法，若存在产生式A-a,则对于任何符号串u和v,有uAv=uav称为从串uAv到uav的一步推导(derivation)。对于任何文法符号串x和y,若x=y或者x经过若干步推 导可产生y,则称x推导或者生成y,记为x=*y。例2.2在例1.4的文法G1中，从A出发推导nnn,从B出发推导vvv,从S出发推导nnvv。A=nA=nnA=nnnB=vB =vvB =vvvS=AB=nAB=nnB=nnvB=nnvv习惯上我们总是对于当前字符串中最左边的变元进行推导，这称为最左推导(left-most derivation)o今后， 在没有说明的情况下，所说的推导默认为最左推导。上述推导过程需要重复写出已推出的字符，比较麻烦，更简便的方式是用推导树记录推导过程。定义2.3推导树：以变元为根和内结点，从一个变元推导出的字符从左到右分别是该结点的子结点，所 有树叶从左到右构成所推导的串。例 4.2 A-0A|0 A-1A|1该文法所生成的语言是(0|1)+，即所有非空的二元串。练习4.3为下列正规语言设计上下文无关文法：(1) 含偶数个0的二元串。(2) 长度为偶数的二元串。从上面的例子和练习，读者可以看到用递归产生式可以实现语言的星闭包运算。下面我们将看到， 用递归产生式还可以生成左右匹配的串，即语句内部的对称结构。例如下列语言中的语句都具有某种对 称结构：L1 = 0n1n | n 1L = wr I w e 0,1+这些语言分别由下列文法生成：G : S r 0S1I01G2: S r 0S0I1S1I00I11我们知道，这些语言都不是正规语言，不能用正规表达式或者有限自动机进行定义。因此，上下文无关 文法的语言描述能力是比较强的，其秘密就在于递归产生式，可以生成左右匹配的字符串。4.歧义文法从推导树看句子的短语结构：（1）句子由短语组成，短语之间有两种关系：即结合关系和构成关系。结合关系是指若干相邻短语之间 结合在一起构成上层短语；构成关系是指一个短语是另一个短语的成分。（2）根据推导树可以看出所推出的句子的短语结构，即识别出该句子的所有短语及其之间的结合关系和 构成关系。因此，推导树也称为语法分析树（parsingtree）。语法分析：在程序编译技术中，需要对源程序进行语法分析，其主要目的是构造源程序的语法分析树。 有一类方法是从根开始往下构造语法分析树，这种构造方法称为自上而下的语法分析，其实质是为源程 序构造最左推导。定理5.1推导树与最左推导是一一对应的。证明：用归纳法可证明，由最左推导只能构造出唯一的推导树，而由推导树也只能构造出唯一的最左推 导。因此，二者是一一对应的。句子的语法结构是其语义的决定因素之一。不同的语法结构往往导致不同的语义。定义5.2若在某文法下一个字符串有两个不同的最左推导，则该文法是歧义的（ambiguous九例5.3在下列文法GE中，i+i*i有两个不同的最左推导，所以是歧义文法。EfE+E I E*E I （E） I i根据第1个推导树分析得的语法结构，i+i*i应解释为先做加法然后做乘法；而第2个推导树所确定的语 法结构则表明，应先做后面的乘法再做前面的加法。因此，根据该文法无法确定一个正确的语义。例5.4例5.3中的歧义文法可改写为如下非歧义性文法。EE+TITTT*FIFF(E)I i定理5.6上下文无关文法的歧义性是不可判定的。定理5.7上下文无关语言的固有歧义性是不可判定的。