模式识别导论（七）.ppt

文档介绍：第七章        句法结构模式识别
形式语言概述
文法推断
句法分析
自动机理论
误差校正句法分析
§7-1 形式语言概述
一、基本概念
1、字母表:与所研究的问题有关的符号集合。
例:V1={A,B,C,D}, V2={a,b,c,d}
2、句子(链):由字母表中的符号所组成的有限长度的符号串。
3、句子(链)的长度:所包含的符号数目。例: |a3b3c3|=9
4、语言:由字母表中的符号组成的句子集合,用L表示。
例:字母表V={a,b}
L1={ab,aab,abab} 有限语言
L2={anbm|n,m=0,1,2….}无限语言
5、文法:在一种语言中,构成句子所必须遵循的规则的集合,用G表示。L(G)表示由文法G构成的语言。
6、V*:由字母表V中的符号组成的所有句子的集合,包括空句子λ在内。例: V*={λ,01, 001}
7、 V+:不包括空句子在内的句子集合,即V+=V*-(λ)
8、VT: 终止符,不能再分割的最简基元的集合,用小写字母
表示。 VT={a,b,c}
9、 VN: 非终止符,由基元组成的子模式和句子的集合。用大
写字母表示。VN={A,B,C}
VT, VN的关系: VT∩VN= Φ(空集)
VT∪ VN= V(全部字母表)
10、产生式(再写规则)P:存在于终止符和非终止符间的关系式。
例: α→β, α∈ VN ,β∈ VN, VT.
11、文法的数学定义:它是一个四元式,由四个参数构成。
G={VN, VT, P, S}
二. 短语结构文法
1. 0型文法(无限制)
设文法G = (VN,VT, P, S)
VN :非终止符,用大写字母表示
VT: 终止符,用小写字符表示
P:产生式
S:起始符
产生式P:α→β, 其中α∈V+,β∈V* α,β无任何限制
( V+不包括空格,V*包括空格)
例:0型文法 G = (VN,VT, P, S)
VN = {S, A, B}
VP = {a, b, c}
P: ① S→aAbc ②Ab→bA ③ Ac→
④ bB→Bb ⑤ aB→aaA ⑥ aB→λ(空格)
S→Aa bc→abAc→→→
此文法可以产生:X=anbn+2cn+2 n≥0
X|n=0=
由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 = (VN,VT, P, S)
VN = {S, B, C} VT = {a, b, c}
P: ① S→aSBC ② CB→BC ③ S→abC ④ bB→bb
⑤ bC→bc ⑥
λ1Sλ2→λ1aSBCλ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→→→→
∴X=a2b2c2

此文法G可产生的语言:L(G)={|n=1,2...}
假设基元
语言L(G)可以描述不同的三角型
X= abc X= a2b2c2
a
b
c
①
②
③
④
⑥
⑤
a
b
c
c
c
b
b
a
a
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
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+