6、V:由字母表V中的符号组成的所有句子的集合,包括空句子 A在内。例:V={A,01,001} 7、V+:不包括空句子在内的句子集合,即V=V-(入) 8、V1;终止符,不能再分割的最简基元的集合,用小写字母 表示。Vr{a,b,c 9、V:非终止符,由基元组成的子模式和句子的集合。用大 写字母表示。VN={AB,C} V,Ⅵ的关系:V∩V=(空集) Vr∪V=∨(全部字母表) 10、产生式(再写规则)P:存在于终止符和非终止符间的关系式。 例:α→β,a∈M,β∈WⅥ 11、文法的数学定义:它是一个四元式,由四个参数构成 G=VN.VI P,S]
6、V* :由字母表V中的符号组成的所有句子的集合，包括空句子 λ在内。例： V* ＝{λ,01, 001} 7、 V＋:不包括空句子在内的句子集合，即V＋＝V*－(λ) 8、VT : 终止符，不能再分割的最简基元的集合，用小写字母 表示。 VT={a,b,c} 9、 VN: 非终止符，由基元组成的子模式和句子的集合。用大 写字母表示。VN={A,B,C} VT， VN的关系： VT∩VN= Φ(空集) VT∪ VN= V（全部字母表） 10、产生式(再写规则)P：存在于终止符和非终止符间的关系式。 例： α→β， α∈ VN ，β∈ VN, VT. 11、文法的数学定义：它是一个四元式，由四个参数构成。 G={VN, VT, P, S}
终止符组成的字符串: 用英文字母表尾部的小写字母x,y,v,w等表示 终止符和非终止符组成的混合字符串 用希腊字母a,B,y等表示。 性质:V∪vx=V(字母表)V∩V=p(空集) P:生成式的有限集。用文法产生句子时的重写规则 P:a→>B 字符串 替换 字符串 S:起始符,代表模式本身,特殊的非终止符 用生成式构成句子时,必须由左边是S的生成式开始
终止符和非终止符组成的混合字符串： 用英文字母表尾部的小写字母x，y，v，w等表示。 终止符组成的字符串： 用希腊字母α，β，γ等表示。 性质： VN VT =V （字母表） VN VT = （空集） P：生成式的有限集。用文法产生句子时的重写规则。 P： → 字符串 替换 字符串 S：起始符，代表模式本身，特殊的非终止符。 用生成式构成句子时，必须由左边是S的生成式开始
一种语言有一种文法,由文法G构成的语言用L(G表示: L(G)={x|x∈V,且S→x} 文法G构成的句子V中字符组成的文法G的 由终止符组成所有句子的集合推导关系 “≥”零次或多次地应用推导关系 “S→x”:句子x从起始符S开始利用文法G的生成式, 经逐步推导得到
一种语言有一种文法，由文法G构成的语言用L(G)表示： ( ) { | , } * L G x x V S x G T = 且 文法G构成的句子 由终止符组成 VT中字符组成的 所有句子的集合 文法G的 推导关系 “ G ” ：零次或多次地应用推导关系 G “ S x G ”：句子 x 从起始符 S 开始利用文法 G 的生成式， 经逐步推导得到
例61给定文法G=(V,Vr,P,S),其中VN={A,B,S}, r={a,b,c},P的各生成式为 ①S→ac,②A→、aAc,③A>B ④B→>bB,⑤B>b 判断x=abc是否属于语言L(G)? Hl: SaAc aaAcc aaBcc aabcc 是 说明: 利用文法构成句子时,除第一个生成式必须利用左边 为起始符S的生成式外,其余生成式使用的先后次序及重 复使用的次数都不受限制
例 6.1 给定文法 G (V ,V , P, S ) = N T ，其中 V {A, B, S} N = ， V {a, b, c} T = ，P 的各生成式为 ①S →aAc，② A→aAc，③ A → B ④ B →bB ，⑤ B →b 判断 x = aabcc 是否属于语言 L(G ) ？ S aAcaaAccaaBcc aabcc ① ② ③ ⑤ 利用文法构成句子时，除第一个生成式必须利用左边 为起始符 S 的生成式外，其余生成式使用的先后次序及重 复使用的次数都不受限制。 是 说明： 解：
短语结构文法 0型文法(无限制) 设文法G=(VAVr,P,S) VN:非终止符,用大写字母表示 Vr:终止符,用小写字符表示 P:产生式 s:起始符 生式P:α→β,其中α∈V,β∈Vα,β无任何限制 (V不包括空格,V包括空格) 例:0型文法G=(NV,P,S) N=S, A,B] P:①S→aAbc②Ab→bA③Ac→Bbcc ④bB→Bb⑤aB→aAaB-→N(空格)
二. 短语结构文法 1. 0型文法（无限制） 设文法G = (VN ,VT , P, S) VN ：非终止符，用大写字母表示 VT： 终止符，用小写字符表示 P：产生式 S：起始符 产生式P：α→β， 其中α∈V+ ，β∈V* α，β无任何限制 ( V+不包括空格,V*包括空格) 例：0型文法 G = (VN ,VT , P, S) VN = {S, A, B} VP = {a, b, c} P: ① S→aAbc ②Ab→bA ③ Ac→Bbcc ④ bB→Bb ⑤ aB→aaA ⑥ aB→λ(空格)