理论计算机复习整理.docx

1.形式化2形式语言3数理逻辑：4理论计算机科学理论计算机科学是关于计算、算法、程序和计算机的数学理论。有许多分支，包括计算理论、.形式语言 理论、形式语义理论，等等。2将以下NFA转化为等价的DFAo据此画出状态转移图如下:证明设M, N分别是接受A和B的两个DFA。证毕正规语言的泵引理定理2.1设是正规语言，那么存在一个常数匕对L中任何长度不小于攵的串卬，存在x,yz,使得川二肛z 且xyhVz 0. xyz g L.证明 设M是接受L的DFA,有k个状态。设卬=。2。 ，其中吟k。那么M从开始状态处理 完W共经历n+1个状态，分别记为外,名,外。注意到n+lNk+1。因为M只有k个不同的状态，所 以在这n+1个状态中的前k+1个状态中一定有一个两个状态是相同的。令这两个状态为么其中 0rsl用归纳法不难证明上述结果是正确的。同理，由第3个方程可求得(B) = vz|zl再由第1个方程立刻可得L(S) = |51这就是Gi所生成的语言。顺便说一下，如果我们把文法Gi中的终极符号n和v分别理解为名词和动词，那么根据A的产生式, A可理解为由名词组成的名词短语，根据B的产生式，B可理解为由动词组成的动词短语，从而根据S 的产生式可知S所指代的语句是由名词短语连接动词短语所组成的。2 .推导在乔姆斯基的文法理论中，把产生式用作推导规那么(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的文法Gi中，从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 A0A|O Afi A|1该文法所生成的语言是(0|1)+,即所有非空的二元串。练习4.3为以下正规语言设计上下文无关文法：(1) 含偶数个0的二元串。(2) 长度为偶数的二元串。从上面的例子和练习，读者可以看到用递归产生式可以实现语言的星闭包运算。下面我们将看到， 用递归产生式还可以生成左右匹配的串，即语句内部的对称结构。例如以下语言中的语句都具有某种对 称结构：L=0T|21L2 = 1WWR I WG 0,1+这些语言分别由以下文法生成：G :S f0Sl|01G2:S0S0|lSl|00|ll我们知道，这些语言都不是正规语言，不能用正规表达式或者有限自动机进行定义。因此，上下文无关 文法的语言描述能力是比拟强的，其秘密就在于递归产生式，可以生成左右匹配的字符串。4.歧义文法从推导树看句子的短语结构：(1)句子由短语组成，短语之间有两种关系：即结合关系和构成关系。结合关系是指假设干相邻短语之间 结合在一起构成上层短语；构成关系是指一个短语是另一个短语的成分。(2)根据推导树可以看出所推出的句子的短语结构，即识别出该句子的所有短语及其之间的结合关系和 构成关系。因此，推导树也称为语法分析树(parsing tree)。语法分析：在程序编译技术中，需要对源程序进行语法分析，其主要目的是构造源程序的语法分析树。 有一类方法是从根开始往下构造语法分析树，这种构造方法称为自上而下的语法分析，其实质是为源程 序构造最左推导。定理5.1推导树与最左推导是一一对应的。证明：用归纳法可证明，由最左推导只能构造出唯一的推导树，而由推导树也只能构造出唯一的最左推 导。因此，二者是一一对应的。句子的语法结构是其语义的决定因素之一。不同的语法结构往往导致不同的语义。定义5.2假设在某文法下一个字符串有两个不同的最左推导，那么该文法是歧义的(ambiguous )。例5.3在以下文法GE中，i+i*i有两个不同的最左推导，所以是歧义文法。EE+E | E*E I (E) I i根据第1个推导树分析得的语法结构，i+i*i应解释为先做加法然后做乘法；而第2个推导树所确定的语 法结构那么说明，应先做后面的乘法再做前面的加法。因此，根据该文法无法确定一个正确的语义。例5.4例5.3中的歧义文法可改写为如下非歧义性文法。E - E+T|TTT*F|FF-(E)| i定理5.6上下文无关文法的歧义性是不可判定的。定理5.7上下文无关语言的固有歧义性是不可判定的。.正规表达式转化为带空转移的NFA定义2.1我们用正规表达式标记有限自动机中的转移，表示该转移可以处理该正规表达式所表示的任何 输入串，这种有限自动机称为广义有限自动机，简称GFA。GFA拆分法：将正规表达式转化为等价的lNFA。.将有限自动机转化为正规表达式GFA去状态法 第1步去掉陷阱状态。第2步添加两端状态。在自动机转移图的两端添加一个新的开始状态X和一个新的接受状态Y,让X 空转移到原来的开始状态，并且让原来所有接受状态空转移到Yo 第3步合并转移。合并两个状态之间的所有方向相同的转移为一个转移，其标记为所有被合并的转移上 的标记的并。如以下图所示。第4步挖去内部状态。去掉一个内部状态，将该状态的每个入转移与每个出转移分别连接为一个转移。 m个入转移与n个出转移相互连接后形成mn个新转移。设一对入转移和出转移上所标记的正规表达式 分别为w和v,那么连接后新转移上的标记如下定义：假设被去掉的状态上没有指向自己的转移，该标记为 WV；假设被去掉的状态上有一个标记为r的环，那么该标记为wr、。如以下图所示。第5步 重复第3步和第4步，直到只剩下状态X到和Y以及二者间的一条转移，那么该转移上的正规表达 式就是所要求的结果。3,将带空转移NFA转化为DFA的方法定义4.1(空转移闭包或.闭包)对于带空转移的NFA来说，其某个状态q的空转移闭包，记为-Oosure(q), 是由该状态自身，以及该NFA从此状态出发，经过假设干次空转移后，所能到达的所有状态构成的集合。根据定义不难计算空转移闭包。我们可以在状态转移图上，跟踪空转移，标记出所有空转移所到达的状 态，然后将这些被标记的状态一一添加到所要求的闭包中即可。状态子集闭包法将s-NFA转化为等价DFA,按如下3步构造该DFA的转移矩阵。第1步，算出e-NFA的开始状态的-闭包，作为DFA的开始状态。第2步，为每个DFA状态构造后继状态。令R为DFA的一个状态，a是一个输入符号。我们构造R的 a-转移后继状态S如下。S = 6-Closured | 3p g R.q g 5(,)即，假设H某状态p经过a转移可到达状态q,那么将q添加到S中，当没有状态可以添加时，再对S求空转 移闭包。此时所得的S就是R的a转移后继状态。第3步，将含NFA接受状态的DFA状态都指定为接受状态。第6讲 米希尔-奈罗德定理与DFA最小化一个正规语言的DFA是无穷多的，其中状态数最小的称为最小DFAo在实际应用中，作为一种算法, DFA当然是越小越好。本讲讨论如何将一个DFA等价变换为最小DFAo这个等价变换的理论基础是米 希尔-奈罗德定理。3 .等价类：相互等价的所有元素构成的集合称为一个等价类。元素x所在的等价类记为x。注意，x与y要么相等要么不相交。n4 .集合的划分:设4h ，是a的一组子集。假设4互不相交且a=u a，那么称a Z=1是A的一个划分(partition)。命题1.设R是A上的一个等价关系，那么R的所有等价类构成A的一个划分。命题2.设口是集合A的一个划分。定义A上二元关系An如下：xRny当且仅当存在4 II, X, y 4那么心是等价关系。推论3.一个集合上的等价关系与该集合的划分是一一对应的。1 .字符串集合上的两个等价关系我们先回顾一个定义，即有限自动机的状态所接受的语言。设M是一个有限自动机，“是其状态。 假设M从开始状态出发处理完串x后恰好到达状态外那么称q接受底夕接受的所有串构成q所接受的语言, 记为q)假设M是DFA,那么M可以确定地处理完任何串并且到达某个唯一状态，所以M的不同状态所接 受的语言是不相交的。因此，DFA各状态所接受的语言构成了输入串集合的划分。这个划分定义了一个等 价关系：假设两个输入串被DFA的同一个状态所接受，那么称这两个串在该有限自动机下是等价的。x定义1.2设/是一个DFA,其输入符号表为Z。我们在输入串集合Z*上定义二元关系Rm如下Rm= (%被M的同一个状态所接受显然Rm是2上的等价关系，称之为M中的等价关系(equivalence in M)。定义1.3设L是一个语言，其符号表为E。我们在Z*上定义二元关系&如下,R广(x, y)|(X/z)xz L = yz “读者不难验证&是E*上的等价关系，我们称之为关于L的等价关系(equivalence toward L)o也许更文 艺点，可称之为“走向L的等价关系”。我们可以这样来理解该等价关系。令x为一个串，那么任何串z作为后缀连接到x上只能导致两个结 果，即要么xz在L中要么xz不在L中。前者将x带到了 L中，后者将x带到了 L外。反过来，我们看到所有串Z被X划分为两类，即zeEIxzeL和Zf IxzeL。前者可以视为X的正确向导 集，后者为x的错误向导集。因此，当且仅当两个串的正确向导集相同时才是关于L等价的。引理1.4设L是正规语言，M是接受L的DFA,那么RM C & ,从而L的等价类数小于等于M的状态 数。证明：设L的字母表为2,以下所讨论的串都是该字母表上的串。设(羽)氏加，那么对任何”2*,有(xz. yz) e ,从而有xzeLo yzeL,即(x,y)H这证明对于任何串乂我们将X在等价关系Rm和&下的等价类分别记为印M和印L.由于Rm7小，我们有=划因此，的等价类个数大于等于&的等价类个数。又由于Rm的等价类就是各状态所接受的语言，从而与这 些状态是一一对应的，所以Rm的等价类个数等于M的状态数。这证明引理的第二个结论成立。 我们将用Rl的等价类作为状态构造一个接受L的最小DFAO2 .米希尔奈罗德定理定理2.1 (Myhill-Nerode) 正规语言L的最小DFA的状态个数恰好等于Rl的等价类个数。证明：1.构造最小DFA。根据上面的引理，&的等价类个数是有限的，我们用这些等价类作为有限自 动机的状态构造一个DFA如下：其中状态集。=*/&,即&等价类集合，2是L的符号表，开始状态S=，Qf=xxeL9即L内的串的 等价类都是接受状态，L外的串的等价类都是非接受状态，对于任何状态国和符号2 ,S(x.a) = xa9即自动机在状态区下扫描字符时就进入状态比旬。2 .论证Ml的正确性。我们对输入串的长度用归纳法，将证明对于任何输入串龙2* ,有x e L(x)由于同是也 的开始状态，所以2心(幻)。假设对于任何长度不超过某个数的串， 都有 xeL(x)o令。为任一输入符号。根据假设，也在处理完X后进入状态印。根据Ml的转移函数， Ml在状态印下处理字符。后进入状态M,所以m被状态刈所接受。这样我们就证明了断言(2.1.1)。 由此不难推出如下结论：对于任何输入串x,都有L(x)=x事实上，令yx,那么因=回，从而y(对),所以%口，(%)。下面证明L(x)7幻。令Z G (%) o我们只需证明Zx。根据(2.1.1),我们有ZL(z)。因此，Z既被状态区所接受又 被状态国所接受。由于Ml是DFA,接受输入串的状态只能是唯一的，所以印二。于是我们有Zx。 这样我们就证明了乙(幻)=同。由此可知，也接受的语言就是乙.论证Ml的最小性。根据上面的引理1.4,立刻可知Ml是最小DFA。推论2.2如果不考虑状态名称上差异，那么每个正规语言的最小DFA是唯一的。证明：设M是正规语言L的最小DFAO M只要更改各状态的名称就完全变为定理2.1证明中所构造的 Ml。由于M是L的最小DFA,根据Myhill-Nerode定理，M的状态个数二&的等价类个数。因此，Rm的等价类个数二Rl的等价类个数。根据上面的引理， RmCl， 从而Rm =Rl.由此可知，对于任何输入串x, M中都有相应地存在唯一状态q恰好接受x的等价类，即L(q)=x。因此，M中各状态与其所 接受的等价类之间是一一对应的。我们将接受区的状态改名为集合区。注意，由于不同状态所接受的等 价类是不相交的，所以这个改名是可行的，即不会导致两个不同状态使用同一个名称。令a是任何输入 符号，那么改名后的M在状态区下处理a后进入某个后继状态。由于该后继状态接受xa,所以该后继状 态所接受的等价类应当是xa,从而该状态为xa。由此可以看出，改名后的M完全变成了定理2.1证明 中所构造的私。3. DFA的最小化方法首先，删除所有的无用状态，即从起始状态出发不能到达的状态。这样做并不改变原DFA的识别功能。其次，对DFA的状态集合进行分割。定义3.1设M是一个DFAoM的任何终止状态与非终止状态是可别离的。1) M的两个状态p与q是可别离的，当且仅当存在串w分别从这两个状态出发可以到达终态与非终态。引理3.2对于状态p和q,假设存在字符a,使得状态b(p,a)与3(q,a)是可别离的，那么p与q是可别离的。U评氏可别离引理3.3对于状态p和q,假设存在某个状态既与p不可别离又与q不可别离，那么p和q是不可别离的。状态分割法：第1步，将终止状态与非终止状态相别离，得初步划分(Q-Q，Qf)第2步，对当前划分中的每个子集做进一步的划分。方法如下：以当前所得的划分为标准，应用引理 3.2和3.3,确定当前子集中的所有可别离的状态对，据此划分该子集。重复第2步，直到没有可别离状 态对时为止。注：根据引理3.2不难看出，状态分割法是正确的，即对于任何DFA,根据该方法所构造的DFA是等价 的并且是最小的。例3.4给定NFA图O 1用状态子集法得DFA现在我们需要最小化该DFA。解：该DFA的状态集记为Q=0,1,2,3,4,5首先将Q划分为拒绝状态集和接受状态集等两个局部。口户0,1,2, 3,4,5其次，对当前划分中的集合继续尝试划分。口2=01,2, 3,4,5口3=0,1,2, 3,4,5根据口3, 3,4,5中不存在可别离的状态对，所以“3就是最后所得的划分。最后，画出所得最小DFA如下。4.用Myhill-Nerode定理证明非正规语言定理4.1 (Myhill-Nerode)语言L是正规的当且仅当&的等价类个数是有限的。证明：假设L是正规语言，那么根据引理1.4, 及有有限个等价类。反之，假设&有有限个等价类，那么根据 Rl,可以按照Myhill-Nerode定理2.1证明中的方法构造出接受L的有限自动机区,所以L是正规语言。 例4. 1用Myhill-Nerode定理证明L二值叱5工1不是正规语言。关键：找出无限个等价类。证明：设/nW孔。注意到aWEL且优任。根据Rl的定义可知,an与心不等价。因此，侬和a叫是两个不相同的等价类。从而L有无限多个等价类。根据Myhill-Nerode定理，L不是正规语 言。练习4.2用Myhill-Nerode定理证明L=卬诚卬(0|1)+不是正规语言。1. 正规语言类的封闭性根据本讲义的定义易知，正规语言类在并、连接和星闭包等正规运算下都是封闭的。定理假设A是正规语言，那么A，是正规语言。注：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-转移后继状态为（3）对于MN的任何状态（p,p）该状态是MN的接受状态当且仅当p和p，分别是M和N的接受状态。例L3令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恰好接受ARO证毕定理L8假设A, B是正规语言，那么A/3 = z|存在使彳导X =尸是正规语言。