形式语言与自动机文法的一般理论.ppt

**南京航空航天大学计算机学院胡军语言?文法例2.11构造一个文法，使其能产生语言Ｌ＝{ｗｗＲ∣ｗ∈{a，b}*}。w是由a和b以任意次序组成的串（包括空串），wＲ是w的逆转，wwＲ是由偶数个a，b组成且由中心开始左右对称的串，如abba，baaaab，aabaabaa等等。例2.12构造一个文法，使其能产生语言Ｌ＝{anbncn∣ｎ≥1}。（不太容易）**南京航空航天大学计算机学院胡军文法等价定义2.4对于两个不同的文法G1＝(V1，T1，P1，S1），G2＝(V2，T2，P2，S2)，如果Ｌ(G1)＝Ｌ(G2)，则称文法G1与G2等价。同一个语言可以由不同的文法产生。在例中已经看到，一个很简单的语言{an|n≥1}就可由三个不同的文法产生。文法是用四元组定义的，在两个四元组的各对应部分中，只要有一点点不同，就应当看作是不同的文法。如在一个已有的文法上，随意加上一些变元，一些终结符，或一些不影响S推导结果的产生式等等，都会变成新的文法。在这个意义下，任何一个语言都可以有无穷多个文法产生它。*2.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）。*南京航空航天大学计算机学院胡军**南京航空航天大学计算机学院胡军文法的乔姆斯基分类单击此处添加小标题由短语结构文法产生的语言，称为短语结构语言，简记为PSL。单击此处添加小标题由上下文有关文法产生的语言，称为上下文有关语言，简记为CSL。单击此处添加小标题由上下文无关文法产生的语言，称为上下文无关语言，简记为CFL。单击此处添加小标题由正则文法产生的语言，称为正则语言，简记为RL。定义2.6**南京航空航天大学计算机学院胡军**南京航空航天大学计算机学院胡军右线性文法定义2.9对于文法G=(V,T,P,S),如果P中产生式都呈以下形式:A→wA→wB这里A,B∈V,w∈T*,则文法G称为右线性文法。类似地，如果P中产生式都呈A→wA→Bw形式，这里A,B∈V,w∈T*,则文法G称为左线性文法。*右线性文法定理2.2任何由右线性文法产生的语言都能被正则文法产生。证明设L是一个右线性文法G产生的语言，G=(V,T,P,S)。现在由G构造正则文法G′=(V′,T,P′,S)，其中P′的构造为:对于P中形如A→w的产生式,若w=a(a∈T)或w=ε,则已符合正则文法的要求，将它们直接放入P′中。对于w=a1a2…an(n≥2),则引入新变元A1,A2,…An-1,并将以下一组产生式 A→a1A1 A1→a2A2 ┆（*） An-1→an加入P′中。*南京航空航天大学计算机学院胡军南京航空航天大学计算机学院胡军南京航空航天大学计算机学院胡军南京航空航天大学计算机学院胡军本质上就是嵌套的递归结构，但是要注意解释：递归规则的原本应用是从右边到左边，但是在语言、字符串这个场景下，可以很容易看作从左边到右边的推导和产生的过程。！在这种表示法中，用尖括号“”和“”括起来的部分，做为一个整体来看，表示一种语法成分，最终要用具体的字符串集合来定义它，如常量、变量、赋值语句等等。符号“::=”和“∣”是BNF本身使用的符号，前者含有“就是”的意思，后者含有“或者”的意思。例如定义的常量就是0，或者1，或者2，或者3，…，或者8，或者9这十个阿拉伯数字。其他的符号如：iF,tHEn,ElsE,；,:=,，,+,-,*,/，a,b,C,x,y,z,等等都是构成语言的基本符号，也就是字母表中的符号。第五条规则关于语句表的定义，这是一种递归的定义形式。要重点说明：自顶向下和自底向上的过程不同，就是对递归规则的不用应用。从树根语句到下一层当语句，是用了第一条规则—当语句是语句的一种。以当语句为根具有四个孩子结点wHilE、布尔表达式、Do、语句的这棵子树