3.3型文法(有限状态文法) 文法G=( VPS) 产生式P:A→aB或A→a,(对产生式限制最严格) 其中AB∈VN(且是单个字符),a∈Vr(且是单个字符) 由3型文法产生的语言成为3型语言 例:文法G=({S,A},{0,1}PS P:①S→0A②A→0A③A→1 S→>0A→>00A→>000A→>0001 G)={01n=1,2.} 例:构造文法G能产生语言L(G)={xX=010m|nm0 解:G=( VPS) Vr(0,1) P:①S→0B②B→→0B③B→1S④B→0 V(S. B)
3. 3型文法（有限状态文法） 文法 G = (VN ,VT , P, S) 产生式P：A→aB 或A→a， （对产生式限制最严格） 其中A,B∈VN（且是单个字符），a∈VT (且是单个字符) 由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型
图象描述语言(PDL) 头头 1970年,Show提出图像描述语言 任何图象都可用头尾来表示 基元b 定义了四种二元连接算子b/h 尾 尾 a a头与b尾相连 t∠a.ba尾与b尾相连形成两个头 ax a a头与b头相连,形成一头二尾 为ha头连b头,a尾连b尾,形 成一头一尾
三. 图象描述语言（PDL） 1970年，Show提出图像描述语言 任何图象都可用头尾来表示 定义了四种二元连接算子 1. a + b 2. a x b 3. a – b 4. a * b t h a头与b尾相连 h t h a尾与b尾相连,形成两个头 t h t a头与b头相连，形成一头二尾 a头连b头, a尾连b尾，形 成一头一尾 h h t t h t 基元b a b a b a b 头 头 尾 尾
元算子 h 个基元的头或尾可以与另一基元的头或尾相连而成为 模式串,并可设置一些较复杂的联结关系和进行各种运 算 例:文法G=( VPS) a C T -.X BVNES,A, B,C) P:①S→A ②S→B ③A→>(b+(C+c)④B→(d+(a+(-d)* ⑤C→(b+c)*a)
一元算子~ 一个基元的头或尾可以与另一基元的头或尾相连而成为 模式串，并可设置一些较复杂的联结关系和进行各种运 算。 例：文法G = (VN ,VT , P, S) VT = { →, ↗ , ↘, ↓,(),+, -, x, *, ~ } VN = {S,A,B,C} P: ① S→A ② S→B ③ A→(b+(C+c)) ④ B→(d+(a+(~d))*C), ⑤ C→((b+c)*a) h t b h t ~b a b c d
(G)={(b+((b+c)*a)+c);(d+(a+(d))*(b+c)*a) a 导出过程 A B C b+c来 t c*
L(G) = {(b+(((b+c)*a)+c)) ; ((d+(a+(~d)))*((b+c)*a))} b c a a d ~d b b c a c C B S d ~ b + 导出过程 d a + + c * a S A b + C + c b + c * a