例文法G[S]: (1)S→aSBE (2)s→aBE (3)EB→BE (4)aB→ab (5)bB→bb (6)bE→be (7)eE→ee L(G)={a"en≥1 G生成的每个串都在L(G)中 L(G)中的每个串确实能被G生成
例 文法G[S]： （1）S→aSBE （2）S→aBE （3）EB→BE （4）aB→ab （5）bB→bb （6）bE→be （7）eE→ee L（G）={ anbnen | n≥1 } G生成的每个串都在L(G)中 L(G)中的每个串确实能被G生成
文法的等价 3若L(G1)=L(G2),则称文法G1和G2是 等价的。 如文法G1[A]:A→DB与G2[S:S→0S1等价 A→DE S→01 E→AB 0 DB 17
17 文法的等价 z若L（G1）=L（G2），则称文法G1和G2是 等价的。 如文法G1[A]：A→DB 与G2[S]：S→0S1 等价 A→DE S→01 E→AB D→0 B→1
文法的类型 通过对产生式施加不同的限制, Chomsky将 文法分为四种类型: 0型文法:对任一产生式a→β,都有 a∈(VUv)+,β∈(VUVr)* 1型文法:对任一产生式a→β,都有|β|≥|a|, 仅仅S→ε除外 2型文法:对任一产生式a→B,都有a∈V 3型文法:任一产生式a→β的形式都为A→aB或 A→a,其中A∈V,B∈Wy,a∈Vr* 18
18 文法的类型 通过对产生式施加不同的限制，Chomsky将 文法分为四种类型： 0型文法：对任一产生式α→β，都有 α∈(VN∪VT) + ， β∈(VN∪VT) * 1型文法：对任一产生式α→β，都有|β|≥|α|， 仅仅 S→ε除外 2型文法：对任一产生式α→β，都有α∈VN 3型文法：任一产生式α→β的形式都为A→aB或 A→a，其中A∈VN ，B∈VN ，a∈VT *
文法的类型 例:1型(上下文有关)文法 文法G[S]:S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→a BD→bD D→b Aa→bD
19 文法的类型 例：1型（上下文有关）文法 文法G[S]： S→CD Ab→bA C→aCA Ba→aB C→bCB Bb→bB AD→aD C→a BD→bD D→b Aa→bD
文法的类型 例:2型(上下文无关)文法 文法G[S]:S→AB A→BS|0 B→SA|1
20 文法的类型 例：2型（上下文无关）文法 文法G[S]： S→AB A→BS|0 B→SA|1