武汉理工大学：《模式识别》课程教学资源（PPT课件）第6章 句法模式识别

6.2.2文法分类四种类型：0型文法、1型文法、2型文法和3型文法1.0型文法：无约束文法P:α→β其中,αeV+,βeV*2.1型文法：上下文有关文法。P:αAα→a,Ba式中，α和α,称为A的上、下文，α,αV；βEV+，AEV（指V的元及其组成的串）。含意：只有处于α，和α，之间的非终止符或非终止符串才能被β替换，并且代换后的符号数目要大于等于代换前的数目

6.2.2 文法分类 四种类型：0型文法、1型文法、2型文法和3型文法。 1．0型文法：无约束文法。 P：  →  其中，  V + ， 。 *  V 2．1型文法：上下文有关文法。 P： 1 A2 →1 2 式中，1 和 2 称为 A 的上、下文， * 1 2  ,  V ； +  V ， * AVN (指 VN 的元及其组成的串)。 只有处于 1 和  2 之间的非终止符或非终止符串才能被  替换，并且代换后的符号数目要大于等于代换前的数目。 含意：

例6.2设有文法G=(V,VT,P,S)，其中V=(S,B,D，V=la,b,c，P的各生成式为OS→aSBD②S-abD，③DB→BDbBbb，bD>bc，?cD→cc问G是否为上下文有关文法？x=aabbcc是否属于L（G）？解：将P改写如下：aSnaSBD②SanabD③DBBD①abBbb③abDabc?cDncca符合条件，文法G是上下文有关文法。saSBDaabDBDabBDDaabbDD三aabbcDaabbcc属于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 )

3.2型文法：上下文无关文法。P:A→β其中AeV,βeV+例6.3设有文法G=(VN,VT,P,S)，V=(S,A,B)，V=a,b，P的各生成式为①S-→aB,②S-→bAA→a,④A-aS,?A→bAA?B→b，①B→bS,@B>aBBG是否属于上下文无关文法？用G产生一个属于L（G）的句子解：每个生成式的左边都是单变量，右边是非空字符串故G是上下文无关文法

3．2型文法：上下文无关文法。 P： A →  其中 AVN ， +  V 。 例 6.3 设有文法 G (V ,V , P, S ) = N T ，V {S, A, B} N = ， V {a, b} T = ，P 的各生成式为 ① S →aB，②S →bA ③ A→ a，④ A→aS ，⑤ A→bAA ⑥ B → b ，⑦ B →bS ，⑧ B → aBB G 是否属于上下文无关文法？用 G 产生一个属于 L(G ) 的句子。 解：每个生成式的左边都是单变量，右边是非空字符串， 故G是上下文无关文法

属于L(G）的句子：aBabsabbAabbbAAabbbaAabbbaa结果不唯一4.3型文法：正则文法、有限态文法P:A→aB或A→b其中, A,BeV,a,beV.。例6.4设有正则文法G=(V,V,P,S)，其中V=(S,B)V=0,1，P由下列生成式组成：①S-→0B,②B→0B,③B→1B,①B→0判断句子x=00010是否是属于语言L（G）的一个句子？223是S三0B三00B三000B三0001B三00010

S aB abS abbAabbbAAabbbaAabbbaa ① ⑦ ② ⑤ ③ ③ 属于L(G)的句子： 结果不唯一。 4．3型文法：正则文法、有限态文法。 P： A→aB或 A →b 其中， A B VN , ，a bVT , 。 例 6.4 设有正则文法 G (V ,V , P, S ) = N T ，其中 V {S, B} N = ， ={0,1} VT ，P 由下列生成式组成： ①S →0B ，② B →0B，③ B →1B，④ B → 0 判断句子 x = 00010是否是属于语言 L(G ) 的一个句子？ ① ② ② ③ ④ S 0B 00B 000B 0001B 00010 是

后一种文法的限制比前一种文法的限制严格：限制愈多的文法愈容易推断：句法模式识别中多采用上下文无关文法和正则文法6.3模式的描述方法根据结构特征对模式进行描述结构描述法，又称句法表示法。模式的表示：链表示法、树表示法、图表示法。对应的文法：链文法（串文法）、树文法、图文法。还有网文法、阵列文法等。6.3.1基元的确定目前关于基元的确定没有一个通用的解决办法基元的选择遵循两个基本原则

后一种文法的限制比前一种文法的限制严格； 限制愈多的文法愈容易推断； 句法模式识别中多采用上下文无关文法和正则文法。 6.3 模式的描述方法 6.3.1 基元的确定 根据结构特征对模式进行描述。 —— 结构描述法，又称句法表示法。 模式的表示：链表示法、树表示法、图表示法。 对应的文法：链文法（串文法）、树文法、图文法。 还有网文法、阵列文法等。 目前关于基元的确定没有一个通用的解决办法。 基元的选择遵循两个基本原则