①aB→abS→abaB→abab abbA→abba bA→→bas→baaB→baab ba6A→→baba 例:G=(Vr,P,S) ={S,T,「} Vr={a,+,,(,)} P:①S→S+T②ST③T→T*④TF ⑤F→(S)⑥F→a ⑥ S→→S+T→T+T→F+T→aT→a+T杆→a+F*→a+a*F→a+a* a
aB→abS→abaB→abab S abbA→abba bA→baS→baaB→baab babA→baba 例：G = (VN ,VT , P, S) VN = {S, T, F} VT = {a, +,*,(,)} P: ① S→S+T ② S→T ③ T→T*F ④ T→F ⑤ F→(S) ⑥ F→a S→S+T→T+T→F+T→a+T→a+T*F→a+F*F→a+a*F→a+a* a ① ⑦ ③ ④ ③ ⑥ ⑥ ① ① ② ② ② ① ② ④ ⑥ ③ ④ ⑥ ⑥
两种方法替换非终止符 ①最左推导:每次替换都是先从最左边的非终止符开始, 例如上边的例子。我们经常采用最左推导。 ②最右推导:每次替换都是先从最右边的非终止符开始, 例如:S→S+T→S+F→S+a→T+a→F+a→a+a
两种方法替换非终止符： ① 最左推导：每次替换都是先从最左边的非终止符开始， 例如上边的例子。我们经常采用最左推导。 ② 最右推导：每次替换都是先从最右边的非终止符开始， 例如： S→S+T →S+F →S+a → T+a → F+a → a+a
3.3型文法(有限状态文法) 文法G=(VV,P,S) 生式P:A→aB或A→a,(对产生式限制最严格) 其中AB∈(且是单个字符),a∈V(且是单个字符) 由3型文法产生的语言成为3型语言。 例:文法G=(S,A},{0,1,P,S) P:①S→0A②A→0A③A→1 S->0A→>00A>000A>0001 L(G)={0n1n=1,2…} 例:构造文法G能产生语言L(G)={x=0n10m1nm0 解:G=(VVP,S) Vr=(0,1) P:①S→0B②B→0B③B→1S④B→0 ∴VM=(S,B)
3. 3型文法（有限状态文法） 文法 G = (VN ,VT , P, S) 产生式P：A→aB 或A→a， （对产生式限制最严格） 其中A,B∈VN（且是单个字符），a∈V T (且是单个字符) 由3型文法产生的语言成为3型语言。 例：文法G = ({S, A},{0, 1}, P, S) P: ① S→0A ② A→0A ③ A→1 S→0A→00A→000A→0001 L(G)={0 n1|n=1,2...} 例：构造文法G能产生语言L(G) = {x|x=0 n 10m | n,m>0 } 解：G = (VN ,VT , P, S) VT=(0,1) P: ① S→0B ② B→0B ③ B→1S ④ B→0 ∴VN=(S, B)
四种文法的关系: 0型 1型 3型 2型 包含关系:限制不严格的文法必然包含限制严格的文法。 后一种文法的限制比前一种文法的限制严格; 限制愈多的文法愈容易推断 句法模式识别中多采用上下文无关文法和正则文法
四种文法的关系 : 包含关系：限制不严格的文法必然包含限制严格的文法。 3型 2型 1型 0型 后一种文法的限制比前一种文法的限制严格； 限制愈多的文法愈容易推断； 句法模式识别中多采用上下文无关文法和正则文法
6.3模式的描述方法 根据结构特征对模式进行描述。 结构描述法,又称句法表示法 模式的表示:链表示法、树表示法、图表示法。 对应的文法:链文法(串文法)、树文法、图文法。 还有网文法、阵列文法等。 6.31基元的确定 目前关于基元的确定没有一个通用的解决办法。 基元的选择遵循两个基本原则
6.3 模式的描述方法 6.3.1 基元的确定 根据结构特征对模式进行描述。 —— 结构描述法，又称句法表示法。 模式的表示：链表示法、树表示法、图表示法。 对应的文法：链文法（串文法）、树文法、图文法。 还有网文法、阵列文法等。 目前关于基元的确定没有一个通用的解决办法。 基元的选择遵循两个基本原则