符合 chomsky范式文法,文法G2=(VNVp,S) 1123453 Y,Y345,Y45,2Y5,S,A,B} A→Y1Y2345,Y1→a,Y2345→ 345 Y2→b,Y2as→AY 45 45→BY5,Y5-)a S→BA.A→→a.B→b 若x= bababa 用G1导出:S→BA→bA→ babaBa→ bababa, 用G2导出:S→BA→bY1Y2345…→baY2345→ baYyas-babYs-babAYs-babaY → babby- bababa 用原文法G1只用四步可以导出 bababa而用标准文法G2贝 用九步才导出
符合chomsky范式文法，文法G2 = (VN ,VT , , S) VN = { Y1Y2345, Y2Y345, Y45, Y5 , S, A, B} A→Y1Y2345, Y1→a, Y2345→Y2Y345, Y2→b,Y345→AY45, Y45→BY5 , Y5→a, S→BA, A→a, B→b 若x=bababa 用G1导出：S→BA→bA→babABa→bababa, 用G2导出：S→BA→b Y1Y2345...→baY2345→ baY2Y345→babY345 →babAY45 →babaY5 →bababY5 →bababa 用原文法G1 只用四步可以导出bababa而用标准文法G2则 用九步才导出 P
2.格雷巴赫范式( Greibach) 若一个上下文无关文法具有P形式: A→a,A∈Va∈Vpa∈V(带空格)则此文法称为 Greibach范式。 例:上下文无关文法 G=VN,VpP,S) nS, C, Vr=a,b,c) P形式:S→aCbb,C→ acbb c→c 变成 Greibach范式:C→c即C→c符合 Greibach范式,不变 S→aCbb,用S→aCBB,B>b代替 C→aCbb,用C→>aCBB,B→b代替 符合 Greibach范式: P:S→aCBB,C→aCBB,C→c,B→b
2. 格雷巴赫范式(Greibach) 若一个上下文无关文法具有P形式： A→aα, A∈VN , a∈VT , α∈VN * (带空格) 则此文法称为 Greibach范式。 例：上下文无关文法 G = (VN ,VT , P, S) VN = {S,C}, VT = {a, b, c} P形式：S→aCbb, C→aCbb C→c 变成Greibach范式：C→cλ即C→c符合Greibach范式，不变 S→aCbb,用S→aCBB, B→b代替 C→aCbb,用C→aCBB, B→b代替 符合Greibach范式： P: S→aCBB, C→aCBB, C→c, B→b
五高维文法:上面我们介绍的都是一维链(串)文法,为了描 述更复杂的图形、图象,需要用高维文法,包括树文法,图文法, 网文法等等。 1.树文法: 定义:四元组G1=(v,rPS) 其中V=VUVr,r:秩(一个节点的直接分支数) P形式:T→TTT都是树 由G产生的语言叫树语言。 L(G={TT∈TxT→TT∈S},Tz是带有V中结点的树集合 扩展树文法:全部产生式形式 其中x12x2…xn∈Vx∈Vr,n∈r(x) 具有上面产生式形式的树文法称扩展的树文法
五.高维文法：上面我们介绍的都是一维链（串）文法，为了描 述更复杂的图形、图象, 需要用高维文法,包括树文法，图文法, 网文法等等。 1. 树文法： 定义：四元组 Gt = (v, r, P, S) 其中V=VN∪VT ， r: 秩(一个节点的直接分支数) P形式：Ti→Tj Ti ,Tj都是树 由Gt产生的语言叫树语言。 L(Gt )={T| T∈T∑ , Ti→T Ti∈S }, T∑是带有VT中结点的树集合 扩展树文法：全部产生式形式 其中x1 , x2 ... xn ∈VN ,x∈VT， n∈r(x) 具有上面产生式形式的树文法称扩展的树文法。 Gt X x x1, x2… xn
例:G=(v,r,PS) V=V、∪V (S.A. B Ka b) a ),r(a)=(2,0),r(b)=(20),r(k)=2 P:①S→K②A→a③B→+b a ba B a B ④A→a⑤B→b S→K ∴S→K导出树 a B a B a 导出图 aa B →k
例：Gt = (v, r, P, S) V=VN∪VT ＝（S,A,B,K,a,b） VT ＝( →, ↗ ), r(a)=(2,0), r(b)=(2,0), r(k)=2 P: ① S→K ② A→a ③ B→b ④ A→a ⑤ B→b ∴ S→K a b A B A B A B A B a b ① ④ ⑤ a k b A B ① ⑤ ④ S→K a b A B A B ④ ⑤ ② ③ a b k 导出树 导出图 a b a b
例2:在氢云室内用正粒子打击核目标碰撞发出的射线可以用 树文法来描述 树文法G=(v,r,PS),VN=(S,AB),Vr=(a,b) 基本定义: (凸弧) (凹弧) P: S B AABB AAABBB A A a B
例2：在氢云室内用正粒子打击核目标碰撞发出的射线可以用 树文法来描述。 树文法Gt = (v, r, P, S) ，VN＝（S,A,B）， VT ＝(a, b) 基本定义： P: a b (凸弧) (凹弧) S → a | S S → a A B S → a A A B B S → a A A A B B B A → a | A A → a B → a | B B → a