《模式识别原理与应用》课件第7章.ppt

7.5.3上下文无关文法的推断对有限数量的样本来说,总可以推断出正则文法来产生这些样本。正则文法的推断比较容易,但非终止符和产生式的数量太多。而正则文法要用几百个非终止符才能描述的问题,用上下文无关文法可能只需用少得多的非终止符即可描述。上下文无关文法的推断比正则文法的推断复杂,原因在于产生式形式种类较多,由终止符串推断产生式集时,结果不唯一,需要确定最合理的推断结果。1.链重复性试探法链重复性试探法是一种有教师的推断法,通过寻找样本集中的自嵌套结构来推断产生式,具体过程如下:(1)对正样本集R+中的每个链,试探性地删去其中某些子链,同时询问教师余下的部分是否仍属于R+。(2)如果回答余下的部分仍属于正样本集R+,则将删去的子链加以若干重复后重新插回原来的链,再询问教师是否仍属于R+,若回答为“是”,则试探成功,判定推断的文法中存在两个形成自嵌套的产生式。【例7.16】设正样本集R+中有一个样本x=uvu,用试探法求出产生式。解对样本x,试探性地删去一些子链,得到链的集合:u,v,uu,vu,uv然后询问教师集合中哪些链仍属于R+。假定只有v仍属于R+,对集合:u2vu2,u3vu3,…,ukvuk再询问教师是否属于R+,如果回答为“是”,则推断出正样本集R+的文法中存在两个自嵌套结构的产生式:A→uAu,A→v。2.利用正样本集的结构规律利用正样本集的结构规律推断文法的方法是,首先对正样本集的各样本进行分析,归纳得到各样本间的结构规律,然后采用试探的方法获得各产生式。在此,结构规律指利用一个文法的产生式集导出正样本集中各样本的过程和先后次序。【例7.17】设正样本集R+={a+a,a+a+a,a+a+a+a,…},利用样本集的结构规律推断文法。解分析正样本集R+中的各样本,归纳得到它们的结构规律,即R+中的每一个样本都是在前一个样本上再加上“+a”。利用正样本集的结构规律,推断出相应的文法为，，P为，，，。习题7-1设文法G=(VN,VT,P,S),其中,VN={S,B,C},VT={a,b,c},P:S→aSBC,S→abC,CB→BC,bB→bb,bC→bc,cC→cc。试说明G是否是上下文有关文法,并证明x=aabbcc属于L(G)。7-2写出正则文法,能生成语言L(G)={ab,ba,aba,bab,abab,baba,…},其终止符VT={a,b}。7-3用上下文无关文法生成习题7-2中的语言。7-4给定正则文法G=(VN,VT,P,S),其中,VN={S,B},VT={a,b},产生式P:S→aB,B→aB,B→bS,B→a。试求出G所对应的有限状态自动机Af=(Q,Σ,δ,q0,F),使得L(Af)=L(G)。7-5给定上下文无关文法G=(VN,VT,P,S),其中,VN={S,A},VT={a,b},产生式P:S→AA,S→AS,S→b,A→SA,A→AS,A→a。设输入串为x=abaab,用CYK算法分析是否为给定文法产生的句子。7-6给定上下文无关文法G=(VN,VT,P,S),其中,VN={S,A,B},VT={a,b,c,d},产生式P:S→AB,S→a,A→aAb,A→cS,B→Bd,B→a。设输入串为x=acabad,用Earley算法分析是否为给定文法产生的句子。7-7设正样本集R+={101,111},推断出规范确定文法G和导出文法GD。7-8设正样本集R+={101,111},试推断出形式微商文法GC。7-9设正样本集R+={01,1001},试推断出K-尾文法GK。(3)d=2,计算t02、t13和t24:对于t02,因为t01=A,t12=A,P中没有非终止符Y→AA的产生式,所以;对于t13,因为t12=A,t23=B,P中有产生式S→AB,所以t13=S;对于t24,因为t23=B,t34=B,P中没有非终止符Y→BB的产生式,所以。识别矩阵构造完成,如表7-1所示。t0n=t04中