⑥ S→Aabc→→abAc→ abbbcc→ a bbbco→、bbcc 此文法可以产生:X=ab2cm+2n≥0 n=0 =bbcc 由0型文法产生的语言称为0型语言 2.1型文法(上下文有关文法) 设文法G=(V,P,S) 产生式P:a1Aa2→>01Ba2 其中A∈VN,β∈V,a1,a2∈V a1Aa2a1a2或A|s|B 由上下文有关文法构成的语言称为上下文有关语言, 用L(G表示,G1:上下文有关文法
S→Aabc→abAc→abBbcc→aBbbcc→ bbcc 此文法可以产生：X=anb n+2c n+2 n≥0 X|n=0=bbcc 由0型文法产生的语言称为0型语言。 2. 1型文法（上下文有关文法） 设文法G = (VN ,VT , P, S) 产生式P：α1Aα2→α1βα2 其中A∈VN，β∈V+ , α1 ,α2∈V* |α1Aα2 |≤|α1βα2 |, 或|A|≤|B| 由上下文有关文法构成的语言称为上下文有关语言， 用L(G1 )表示，G1：上下文有关文法 ① ② ③ ④ ⑥
例:G=(NVr,P,S) VN={,B,C}Ⅵ={a,b,c} P:①S→aSBC②CB→BC③S→abC④bB→bb ⑤bC→bc⑥cC→cc 入SA2→A1 aSBCa2,bBA→b入 对于S→aSBC a1=入,a2=A,A=S,B=aSBC,并且|S|aSBC .符合1型文法规则 对于bB→bb ∵a1=b,a2=入A=B,B=b,并且門s 也符合1型文法规则 产生式都符合型文法的要求
例：G = (VN ,VT , P, S) VN = {S, B, C} VT = {a, b, c} P: ① S→aSBC ② CB→BC ③ S→abC ④ bB→bb ⑤ bC→bc ⑥ cC→cc λ1Sλ2→λ1 aSBCλ2 , bBλ→bbλ 对于S→aSBC ∵α1= λ, α2= λ, A = S, B=aSBC,并且|S|<|aSBC| ∴ 符合1型文法规则 对于bB→bb ∵α1= b, α2= λ,A = B, B=b,并且|B| ≤ |b| ∴ 也符合1型文法规则 产生式都符合1型文法的要求
s→aSBC→ aabCBC→ abbbCo→ aabbco→ aabbcc→aabb X=ab-C 此文法G可产生的语言:L(G)={a"bcn=1,2} 假设基元 a b 请言L(G可以描述不的三角型 X= abc X abac.c a a a
S→aSBC→aabCBC→abbBCC→aabbCC→aabbcC→aabb cc ∴X=a2b 2c 2 此文法G可产生的语言：L(G)={anb nc n |n=1,2...} 假设基元 语言L(G)可以描述不同的三角型 X= abc X= a2b 2c 2 a b c ① ③ ② ④ ⑤ ⑥ a b c c c b b a a
例62设有文法G=(VN,V,P,S),其中VN={S,B,D} V={a,b,c},P的各生成式为 ①S→aSB,②S→>abD,③DB→>BD ④bB→bb,⑤bD→bc,⑥cD→c 问G是否为上下文有关文法?x=cbbc是否属于L(G)? 解:将P改写如下: ①AS→ASBD,②AS→AmbD,③ADB→、ABDA ④AbB→b,⑤AbD→bC,⑥ACD4→)ACC4 符合条件,文法G是上下文有关文法 ssasbd aabDBD aabBDD多 aabbDD当 aabbcd aabbcc 属于L(G)
① ② ③ ⑤ 例 6.2 设有文法 G (V ,V , P, S ) = N T ，其中 V {S, B, D} N = ， V {a, b, c} T = ，P 的各生成式为 ① S →aSBD ，② S → abD，③ DB → BD ④bB →bb，⑤bD →bc，⑥cD → cc 问 G 是否为上下文有关文法？ x = aabbcc 是否属于 L(G ) ？ 解：将 P 改写如下： ①S →aSBD，②S →abD ，③DB → BD ④bB →bb ，⑤bD →bc，⑥cD → cc 符合条件，文法 G 是上下文有关文法。 ① ② ③ ④ ⑤ ⑥ S aSBD aabDBD aabBDD aabbDD aabbcD aabbcc 属于 L(G )
2.2型文法(上下文无关文法) 设文法G=(NV,P,S) 产生式P:A→甲其中A∈VN(且是单个的非终止符) β∈V(可以是终止符,非终止符,不能是空格) 对产生式的限制比较严格 由上下文无关文法构成的语言称为上下文无关语 例:文法G=(VMVP,S) VN=S,B, Cy V=a T P:①S→aB②S→bA③A→a④A→aS ⑤A→bAA⑥B→b⑦B→bs⑧B→aBB
2 . 2型文法（上下文无关文法） 设文法G = (VN ,VT , P, S) 产生式P：A→β 其中A∈VN（且是单个的非终止符) β∈V+ (可以是终止符，非终止符，不能是空格) 对产生式的限制比较严格 由上下文无关文法构成的语言称为上下文无关语言。 例：文法G = (VN ,VT , P, S) VN = {S, B, C} VT = {a, b} P: ① S→aB ② S→bA ③ A→a ④ A→aS ⑤ A→bAA ⑥ B→b ⑦ B→bS ⑧B→aBB