斜视与弱视的基本知识

1形式语言与自动机（FormalLanguagesandAutomata）第二章文法的一般理论南京航空航天大学计算机科学与技术学院胡军[e-mail]2020年1月1日星期三南京航空航天大学计算机学院胡军22.1问题的提出2.2形式文法与形式语言2.3文法的乔姆斯基分类2020年1月1日星期三南京航空航天大学计算机学院胡军32.1问题的提出任何有意义的语言都不是任意字符串的集合，而是符合某些规则要求的字符串集合.自然语言(英语，语法)；程序设计语言(C语言，文法)；文法(Grammar):用有限个规则描述无穷多字符串的集合自然语言描述(如：英语语法)；严格的形式规则描述（如：C语言文法、Pascal语言文法）--形式文法，形式语言2020年1月1日星期三南京航空航天大学计算机学院胡军4BNF(Backus-NaurForm)例2.1在类PasCal语言中，语句是用下述一组规则定义的：语句::=条件语句∣当语句∣复合语句∣赋值语句条件语句::=IF布尔表达式THEN语句ElSE语句当语句::=WHILE布尔表达式DO语句复合语句::=BEGIN语句表END语句表::=语句∣语句；语句表赋值语句::=变量:=算术表达式布尔表达式::=算术表达式关系运算符算术表达式关系运算符::=||≦∣≧∣=∣≠算术表达式::=常量|变量|（算术表达式算术运算符算术表达式）算术运算符::=+|-|*|/常量::=0|1|2|3|4|5|6|7|8|9变量::=a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z2020年1月1日星期三南京航空航天大学计算机学院胡军5问题的提出例2.2根据例2.1中的各规则，下述的字符串WHILEx≤5DOx:=(x+2)是一个合法的语句;因为：整个符合当语句的定义结构；x≤5是布尔表达式的一种；x:=（x+1）是赋值语句的一种（从而也是语句的一种）；2020年1月1日星期三南京航空航天大学计算机学院胡军6语法树(分析树，ParserTree)2020年1月1日星期三南京航空航天大学计算机学院胡军7问题的提出例2.3用下述语法规则定义英语中的句子。Sentence→NounphraseVerbphraseNounphrase→ArticleNounArticle→the∣aNoun→apple∣cat∣manVerbphrase→VerbNounphrase∣VerbVerb→eats∣sings∣runstheappleruns语法/语义ArticleArticle2020年1月1日星期三南京航空航天大学计算机学院胡军82.2形式文法与形式语言定义2.1一个文法G是一个四元组G=(V,T,P,S)，其中：①V：是变元（Variable，Nonterminal）的有限集。②T：是终结符（Terminal）的有限集。③P：是产生式（Production）的有限集，其中每个产生式都是α→β的形式，其中α∈(V∪T)+，且其中至少有一个V中的符号，β∈(V∪T)*。α称为产生式的左部，β称为产生式的右部。④S∈V，称为文法G的开始符号。(S很重要，决定这组规则最终要定义什么，考虑例2.3中的VerbPhase和Sentence)例2.4:①G1=({A,B},{0,1},{A→0B,B→1B,B→0},A)。②G2=({A,B,C},{a,b,C},{A→aBC,B→b,C→CC,C→ε},A)。③G3=({L,M,N},{0,1,2},{M→0LN,L→1,0L→2,LN→12，N→0}，M)。2020年1月1日星期三南京航空航天大学计算机学院胡军9文法表示方法的约定凡有关文法的例子，都遵循下述的约定：①大写拉丁字母A,B,C,D,E和S等等表示变元，除非另做说明，S表示开始符号。②小写拉丁字母a,b,c,d,e,数字等等表示终结符。③小写拉丁字母u,v,w,x,y,z等等表示终结符串。④小写希腊字母α，β，γ等等表示变元和终结符共同组成的串。另外还约定，同一个文法中如果有若干个左部相同而右部不同的产生式，如：α→β1，α→β2，…，α→βn则可以缩写为：α→β1|β2|…|βn在上述约定下，写一个文法时，只写出它的产生式集合就可以了.2020年1月1日星期三南京航空航天大学计算机学院胡军10字符串的推导与归约定义2.2给出文法G=(V,T,P,S)，我们定义两个字符串之间的一个关系“”：若α=α1α2α3,γ=α1βα3,并且α2→β是P中的一个产生式，则有αγ，此时称由α直接推导出γ。根据第一章关于集合上关系的闭包的定义，我们也可将扩充为，将αγ称为由α推导出γ。若有Sγ，则称γ为句型，当γ∈Ｔ＊，则称γ为句子。对应于推导，还有一个重要的概念，称为“归约”。其定义是：如果αγ是由α到γ的推导，则反过来称γ归约到α，记作γα。GGGGGGGG2020年1月1日星期三南京航空航天大学计算机学院胡军11字符串的推导与规约例2.7对于例2.6中给出的文法G，我们有：S0A100A11000A111000111第一步直接推导用的是第（1）个产生式，第二步直接推导用的是第（2）个产生式，第三步直接推导还是用第（2）个产生式，最后一步直接推导用的是第（3）个产生式。总起来我们也可以写为S000111。在这个推导中，0A1，00A11，000A111,000111都是句型，而000111又是句子。在今后写推导式子的时候，若所指的文法是明确无误的，则可将记号或中的G省略，只写或即可。另外，如果α经过i步的直接推导到β，就可写αβ。GGGGGGGi2020年1月1日星期三南京航空航天大学计算机学院胡军12形式文法与形式语言定义2.3给出文法G=(V,T,P,S)，它所产生的语言记作Ｌ(G)，由下述集合定义：L(G)={ｗ|Sｗ，并且ｗ∈Ｔ*}。换句话说，文法G产生的语言Ｌ(G)，就是由G中开始符号S推导出来的全体终结符号串所构成的集合，也就是句子的集合。2020年1月1日星期三南京航空航天大学计算机学院胡军13文法语言例2.8给出文法G,它有两个产生式：S→aSbS→ab则该文法产生的语言Ｌ(G)={anbn∣n≥1}。这是根据Ｌ(G)的定义，考虑从S的推导，若先用G中第二个产生式，则Sab，就不能再往下推导了，此时相当于语言中ｎ＝1的情况。若从S出发，先用第一个产生式ｎ-1次，即SaSbaaSbb…an-1Sbn-1，最后再使用第二个产生式一次，得到Saｎbｎ，这个推导对于任何ｎ1都是对的。再加上ｎ=1的情况，即可得到L(G)＝{anbn∣n≥1}。2020年1月1日星期三南京航空航天大学计算机学院胡军14文法语言例2.9给出文法G，它的产生式是：S→aB∣bAA→a∣bAA∣aSB→b∣aBB∣bSＬ(G)是由相等个数a和b组成的（次序不限）所有串的集合，加以证明。为了证明最终的结论，要证明以下三个互相关联的命题。①Sｗ，当且仅当ｗ中包含相等个数的a和b。②Aｗ，当且仅当ｗ中a的个数比b的个数多1。③Bｗ，当且仅当ｗ中b的个数比a的个数多1。***2020年1月1日星期三南京航空航天大学计算机学院胡军15文法语言下面我们用关于w长度的归纳法(多重归纳法)来证明上述三个命题。归纳基础∣w∣＝1。命题（2），（3）显然是对的，因为只能有Aa，Bb，用其他产生式时都将推导出长度大于1的串。对于命题（1），因为在∣w∣＝1这个大前提下，一方面不可能有Sw，另一方面ｗ中也不可能包含相等个数的a和b，即“当且仅当”的两个方面都是假的，故命题（1）自然成立。归纳步骤假设对于所有长度不超过k-1的串ｗ，命题（1），（2），（3）成立，现在要证当│w│＝k时（k≥2），命题（1），（2），（3）也成立。*2020年1月1日星期三南京航空航天大学计算机学院胡军16文法语言先证命题（1）。如果Sｗ，那么推导的第一步必然是SaB或SbA。对于第一种情形，必然有ｗ＝aw1，且Bw1，因为∣w1∣＝k－1，则根据归纳法假设，它包含b的个数比a的个数多1（命题（2）），因此ｗ包含a的个数与b的个数相等。对于SbA的情形，证明完全类似。反之，如果∣w∣＝k，且w包含相等个数的a和b，要证Sw。考虑w的第一个符号只有a或b两种情况，若是a，则w＝aw1，且∣w1∣＝k－1。由于w1中包含b的个数比a的个数多1，根据归纳法假设，必有Bw1（命题（3））。此时使S的第一次直接推导为SaB，然后将B推导到ｗ1，最后得到Saw1＝w。对于w以b开始的情况，可以完全类似地证明。考虑再证明命题（2）和（3）。*****2020年1月1日星期三南京航空航天大学计算机学院胡军17语言文法例2.10给出语言Ｌ＝{aｎ∣ｎ≥1}，找出产生它的文法。Ｌ＝{a，aa，aaa，…}，它是一个无限集。因此必须先产生出一个a来，我们首先用产生式S→a来实现。因为Ｌ是无限集，必须用递归的方法，以一个a为基础，不断地添加一个a。即再用一个产生式S→aS，与第一个产生式合起来，整个文法就是：S→aS→aS当然，产生Ｌ的文法不是唯一的，我们也可以用以下两个产生式S→aS→Sa还可以用文法S→aSS→ε2020年1月1日星期三南京航空航天大学计算机学院胡军18语言文法例2.11构造一个文法，使其能产生语言Ｌ＝{ｗｗＲ∣ｗ∈{a，b}*}。w是由a和b以任意次序组成的串（包括空串），wＲ是w的逆转，wwＲ是由偶数个a，b组成且由中心开始左右对称的串，如abba，baaaab，aabaabaa等等。例2.12构造一个文法，使其能产生语言Ｌ＝{anbncn∣ｎ≥1}。（不太容易）2020年1月1日星期三南京航空航天大学计算机学院胡军19文法等价定义2.4对于两个不同的文法G1＝(V1，T1，P1，S1），G2＝(V2，T2，P2，S2)，如果Ｌ(G1)＝Ｌ(G2)，则称文法G1与G2等价。同一个语言可以由不同的文法产生。在例2.2.7中已经看到，一个很简单的语言{an|n≥1}就可由三个不同的文法产生。文法是用四元组定义的，在两个四元组的各对应部分中，只要有一点点不同，就应当看作是不同的文法。如在一个已有的文法上，随意加上一些变元，一些终结符，或一些不影响S推导结果的产生式等等，都会变成新的文法。在这个意义下，任何一个语言都可以有无穷多个文法产生它。2020年1月1日星期三南京航空航天大学计算机学院胡军202.3文法的乔姆斯基分类定义2.5对于文法G＝（V，T，P，S）按以下方法分为四类：①若Ｐ中的产生式，不加另外的限制，则G称为0型文法，或短语结构文法（PSG）。②若Ｐ中每个产生式α→β都满足条件|α|≤∣β|，则G称为1型文法，或上下文有关文法（CSG）。③若Ｐ中每个产生式都具有如下形式：A→β，β∈(V∪T)*，A∈V，则称G为2型文法，或上下文无关文法（CFG）。①若Ｐ中每个产生式都具有如下形式：A→a或A→aB，a∈T∪{ε}，A，B∈V，则称G为3型文法，或正则文法（RG）。2020年1月1日星期三南京航空航天大学计算机学院胡军21文法的乔姆斯基分类定义2.6由短语结构文法产生的语言，称为短语结构语言，简记为PSL。由上下文有关文法产生的语言，称为上下文有关语言，简记为CSL。由上下文无关文法产生的语言，称为上下文无关语言，简记为CFL。由正则文法产生的语言，称为正则语言，简记为RL。2020年1月1日星期三南京航空航天大学计算机学院胡军222020年1月1日星期三南京航空航天大学计算