A VN ， （ VN∪ VT）* ，则G是 一个2型文法。 2型文法对应非确定的下推自动机（PDA）.
例 文法G= （VN，VT，P，S） 其中： VN ={S} VT ={0，1} P={S—>0S1,S01} 为1型文法或上下文有关文法。
２．3型文法（线型文法、正则文法、正规文法
设文法G=（VN，VT，P，S），如果它的 每一个产生式的形式都是A—> B或A —> , 其中A、B VN , VT ， 则G是一个3型文法。（右线性） 3型文法对应有限自动机.
定义２．5 前缀和后缀
设z=xy是字符串. x是z的前缀.y是z的后缀. 如果 y <> , x是z的真前缀. 如果 x<>, y是z的真后缀 例如： z =101 z的前缀有: ,1,10,101, z的真前缀有: ,1,10, z的后缀有: ,1, 01,101, z的真后缀有,1, 01,
定义２．6 子字符串
V=S,W=0011, 直接推导序列 V=S=〉 0S1=〉0011=W，即V=>*W
定义2．15 最左推导
如果在推导的过程中，总是对当前符号串中的最 左边的非终结符进行替换，则称最左推导。
文法 G= （{S，A}，{a,b},P，S）其中P为： (1) S—>aAS （2）A—>SbA （3）A—>SS （4）S—>a （5） A—>ba 一个最左推导序列：
１．０型文法（短语文法）
设G=（VN，VT，P，S），如果对它的每 一个产生式 —> 不加任何限制， 则G是一 个0型文法（短语文法）。 0型文法对应图灵机.（TM ）
例 文法G= （VN，VT，P，S） 其中： VN ={S} VT ={0，1}
P={S—>0S1,S01} 为0型文法。
２．１型文法(上下文有关文法)
定义2．13 直接推导
如 —> 是文法G=（VN，VT，P，S）的一条 产生式，
、（ VN VT ）＊, 若有符号串v,w满足:
v= , w= , 则说v(应用规则α —>β )直接推导出w, 或说,w是v的直接推导, 或说,w直接归约到v, 记作v=>w.
定义2．14 直接推导序列
例如 文法G= （VN，VT，P，S）， 其中VN={S}，
VT={0，1}， P={S0S1, S01}.
２．１．２ 文法的分类
乔姆斯基于1956年建立形式语言的描述， 对程序设计语言的设计、编译方法和计算复杂 性等方面有重大作用。
他把文法分为四类：0型、1型、2型和3型。 这几类文法的差别在于对产生式施加不同 的限制。
第二章 形式语言与自动机理论基础 2．１语言和文法
２．１．１ 基本概念
形式化语言：具有语法严格、结构正规、便于计算机处理
的特点。 一个程序设计语言是一种形式化语言。其核心是语法和
语义。
语法：一组规则，是语言的形式。 语义：是语言的内容。
静态语义：一系列规则，确定哪些合乎语法的程序
是合适的。
动态语义：表明程序要做什么，要计算什么。
定义 ２．１ 字母表
字母表:元素的非空有穷集合. 符号:字母表中的元素. 符号表:字母表. 字母表的表示符号：
定义２．２ 符号串
符号串:由字母表中的符号组成的任何有穷序列.其中符号 的顺序是很重要的. 例如:字母表∑={0,1},00,11,10,01,100 是它上的符号串. 注意:01和10是不同的两个符号串. 符号串的表示:可以使用字母表示符号串.如X=100 符号串的长度:符号串X中字符的个数m,用|X|=m表示. 空符号串:用ε 表示, | ε |=0.
定义２．8 符号串集合的乘积
设A、B是两个符号串的集合， AB表示A与B 的乘积，定义为:
AB={xy|xA yB} 例如 A={a,bc}, B={de,f} AB={ade,af,bcde,bcf} 注意：{}A=A{}=A
A=A =
定义２．9 符号串集合的方幂
设A是符号串集合，则称 Ai是符号串集合A 的方幂，其中i〉=0。具体定义为： A0={} A1=A A2=AA …… An=AAA……A（n 个A）
子字符串:一个非空字符串x,删去它的前缀和后 缀所得的字符串.简称子串. 如果删去的前缀和后缀不同时为,称该子串为 真子串. 例如：x=101 子串有:101,10,1,01,0, 真子串有: 10,1,01,0,
定义２．7 符号串集合
字符串集合:若集合A中的一切元素是某字母表 上的符号串. 例如:={1,0},A={0,1,10,00}
S=>S=> aAS=>aSbAS=>aabAS=>aabbaS=>aabbaa 故S、 aAS、aSbAS、aabAS、aabbaS、aabbaa都
是文法G的句型
定义2．18 句子
设G是一文法， S是文法的开始符号，如果有S=> * , VT * 则 是文法G的句子。
文法 G= （{S，A}，{a,b},P，S）其中P为： (1) S—>aAS （2）A—>SbA （3）A—>SS （4）S—>a （5） A—>ba 一个推导序列： S=> aAS=>aSbAS=>aabAS=>aabbaS=>aabbaa VT *
2．1．４语法树与文法的二义性
定义 ２．２２语法树
设文法G是给定的文法，称满足下列条件的树为G的一棵 语法树。
（1）每个节点都标有G的一个文法符号，且根节点标有初 始符S，非叶节点标有非终结符．
（2）若一节点A有n的儿子节点B1，B2，…，Bn (从左到右 的次序),则A—> B1B2…，Bn 一定是G中的一个产生式。
文法间关系
0型文法 1型文法 2型文法 3型文法
２．１．３ 推导和归约
文法的语言：从文法的开始符号出发，对当前产 生式右部符号串中的非终极符替换为相应产生式 右部的符号，如此反复，直至最终符号串全由终 极符号组成。如此得到的终极符号串的全体，就 是文法所产生的语言。
例 文法G= （VN，VT，P，S） 其中： VN ={S} VT ={0，1} P={S—>0S1,S01} 该文法的语言是０n１ n
S=> aAS=>aSbAS=>aabAS=>aabbaS=>aabbaa
定义2．16 最右推导
如果在推导的过程中，总是对当前符号串中的最 右边的非终结符进行替换，则称最右推导。
文法 G= （{S，A}，{a,b},P，S）其中P为： (1) S—>aAS （2）A—>SbA （3）A—>SS （4）S—>a （5） A—>ba 一个最右推导序列：
设文法G中的任一产生式A —> , 其中 A VN， 、 （ VNVT ）＊ ，
（ VNVT ）+ 则G是一个1型文法。 1型文法对应线性界限机（LBA).
例 文法G= （VN，VT，P，S） 其中： VN ={S} VT ={0，1} P={S—>0S1,S01} 为1型文法或上下文有关文法。
故aabbaa是文法G的句子。
定义2．19 短语
设G是一文法， S是文法的开始符号， 是文法G的一个
句型,如果有:
S=> * A
并且
A=>+ 则称 是句型 相对于A 的短语。
文法 G= （{S，A}，{a,b},P，S）其中P为： (1) S—>aAS （2）A—>SbA （3）A—>SS （4）S—>a （5） A—>ba 一个推导序列： S=> aAS=>aSbAS => aabAS=>aabbaS abba是句型aSbAS相对于A的直接短语。
={ ,a,b, aa,ab,ba,bb, aaa,aab,aba,abb,baa,bab,bba,bbb, ……}
定义２．12 文法
文法G定义为四元组（VN，VT，P，S）。 其中VN为非终结符集, VN非空有穷集
VT为终结符集,VT非空有穷集 VN VT = , V= VN VT P为产生式， P为非空有穷集 S为开始符号或识别符号，是一个非终结符， 至少在一条规则中作为左部出现。
语法树的构造举例。
G= （{S，A}，{a,b},P，S）其中P为：
(1) S—>aAS (2) A—>SbA (3) A—>SS (4) S—>a
一棵语法树为： S
a
A
S
(5) A—>ba
S bA a
a
ba
句型aabbaa的语法树。
文法G:E->E+E|E*E|(E)|i 对句子i*i+i的推导过程如下： 推导1:E=>E+E=>E*E+E=>i*E+E=>i*i+E=>i*i+i 推导2:E=>E*E=>i*E=>i*E+E=>i*i+E=>i*i+ i
定义２．３符号串的连接
连接:符号串x和y,他们的连接是把y的字符写在 x的字符之后. 例如：x=101,y=010 他们的连接xy=101010 |xy|=|x|+|y|=3+3=6
定义２．4 符号串的方幂
方幂:符号串x,把自身连接n次得到的符号串z, z=xxxx…;记为xn
X0= X1=X 例如：X=101 X0= X1=101 X2=101101 X3=101101101
例文法G= （VN，VT，P，S） 其中： VN ={S,A,B}, VT ={0，1} P为: S—>0A ,S1B ,S—>0 ,
A—>0A ,A1B ,A—>0S ,