r(a)=(0,1,2,46),r(b)=(0,1) 射线导出树 射线图: ala|alala|a a|a|a|a a|a|a|a a|a|a|a|a b|b|b b|b|b
r(a)=(0,1,2,4,6), r(b)=(0,1) 射线导出树： S → a a a a a a a a a a a a a a a a a a a b b b b b b b b b b b b b a a b 射线图：
§7-2文法推断 根据已知L(G)样本集导出未知文法G的过程 样本集S三x,X…X),推断算法 G 导师 (一)基本定义 1若在产生式中至少有一个产生式存在以下形式: A→)0AB 此文法G=(VVPS)是循环文法或不确定,由它产生 的语言L(G)为无限的 2若文法G为不循环的,则必为确定的,且L(G)为有限的
§7-2 文法推断 根据已知L(G)样本集导出未知文法G的过程。 (一)基本定义： 1.若在产生式中至少有一个产生式存在以下形式： Ai→αiAi βi 此文法G = (VN , VT , P, S) 是循环文法或不确定，由它产生 的语言L(Gt )为无限的。 2.若文法G为不循环的，则必为确定的，且L(G)为有限的。 样本集 推断算法 Gt St=(x1 , x2… xt ) 导师
3.当L(G)=L(GB)时,则GA与G等效,等价。 例:有限状态文法GA=(VVpP,S),VN={S},Vr={0,1} P:S→→0SS→ 则L(GA)={0 上下文无关文法GB=( VLVP S)2VN={S,A},Vr={0,1} P:S→A1,A→AA,A→0则L(GB)=0m12.} (GA)=L(G1)∴G与G等效 4S是L(G)的子集,即S+∈L(G),称为正取样,S是L(G)子集, 记为S∈L(G)称为负取样, 5若正取样S=(x12x2…x)=L(G),称为S是完备的,负取样 S=(x1,x2…x)=L(G),称S也是完备的, 且S=(S+S)=(x,x2…x=(L(G),(G)也是完备的
3.当L(GA )= L(GB )时，则GA与GB等效，等价。 例：有限状态文法GA = (VN ,VT , P, S), VN = {S}, VT = {0, 1} P: S→0S ,S→1 则L(GA)={0 n1|n=1,2,…} 上下文无关文法GB = (VN ,VT , P, S), VN = {S，A}, VT = {0, 1} P: S→A1 , A→AA , A→0 则L(GB)={0 n1|n=1,2,…} ∴ L(GA)= L(GB ) ∴ GA与GB等效 4.S +是L(G)的子集，即S +∈L(G)，称为正取样， 是 子集， 记为 称为负取样， 5.若正取样S +=(x1 , x2….. xi )= L(G)，称为S +是完备的，负取样 = (x1 , x2….. xi ) = , 称 也是完备的， 且St=(S+ ,S- )=(x1 , x2….. xi )=( L(G), )也是完备的。 S − L(G) − S L(G) − − S − L(G) − S − L(G) −
(二)有限状态文法推断 状态图表示方法,文法可以用图来表示 例:G=( VLVTP S) N=s, A,B,C) Vr={0,1} P:①S→0A②A→0A 0 ③B→0④B→→0B ⑤S→1B⑥A→1B0(A 0 B ⑦C→0C⑧S→1C ⑨A→1⑩C-1 T:附加状态 此文法可以产生的字符串 T X1=001,x2=0m+10m+l2 x,=10t1x,=10n1
( 二 ) 有限状态文法推断 状态图表示方法 ，文法可以用图来表示 例： G = (V N ,V T, P, S) V N = {S, A, B, C} V T = { 0 , 1 } P : ① S→ 0 A ② A→ 0 A ③ B→ 0 ④ B→ 0 B ⑤ S→ 1 B ⑥ A→ 1 B ⑦ C→ 0 C ⑧S→ 1 C ⑨ A→ 1 ⑩ C→ 1 T：附加状态 此文法可以产生的字符串 x1=00n1, x2=0 n+ 110m+ 1 , x 3 =10n+ 1 , x4 =10 n 1 A S C BT 0 0 0 0 1 1 1 1 1 0
规范确定文法 已知正取样S+=(x,x2x) 推断规范文法G。=( VLVP S)的步骤如下 ①VT=S+中不同的终止符 ②2设x=a1a2a1n链 P1S→>312i1 Zn∈VNa1∈Vr >a; Z:∈V,a:2∈V n2→~a1n-1inl a:∈V VNS,Zi il2i2… 此文法产生的语言是确定的,有限的,且有性质:L(G1)=S+
一.规范确定文法 已知正取样S +=(x1 , x2….. xn ) 推断规范文法Gc = (VN ,VT , PL , S)的步骤如下： ①VT = S +中不同的终止符 ② 设xi = ai1 ai2 ... ain链 ∴PL : S→ai1Zi1 Zi1∈VN , ai1∈VT Zi1→ai2Zi2 Zi2∈VN , ai2∈VT … ZIn-2→ain-1Zi n-1 Zin-1∈VN , ain-1∈VT ZIn-1→ain ain∈VT ∴VN={S, Zi1 ,Zi2 ,... Zin-1 , } 此文法产生的语言是确定的，有限的，且有性质：L(GL )=S+