ѧ
JOURNAL OF SOFTWARE
1999 10 8 Vol.10 No.8 1999



ķƶоʷ״

ժҪķƶʽԵĹѧϰ,оδԵϢ,ͨƶϵõԵ﷨.ķƶоʷ״.Ȳķƶϵģ,޹ķ༰ƽࡢɷģԼ޹ķƶϷ,ķƶϵӦ,չ䷢չ.
ؼʡʾѧϰ,ƶ,ʽԵѧϰ,ķƶ.
ͼšTP
Grammatical Inference: Retrospect and Prospect
ZHANG Rui-ling
(Laboratory of Computer Science Institute of Software The Chinese Academy of Sciences Beijing 100080)
Abstract Grammatical Inference (GI) is a problem of inductive learning of formal languages, which deals with how to obtain the grammatical description of a formal language from given finite data drawn from the language. In this paper, the authors provide a survey of the history and recent advances in GI field. They first present some learning models for GI. Then, they enumerate methods for GI with an emphasis on the results concerning the inference of context free grammar class and its some subclasses, hidden Markov models, and stochastic context-free grammar class. At last, they briefly give some applications of GI as well as the future directions of GI research.
Key wordsLearning from examples, inductive inference, learning of formal languages, grammatical inference.
ķƶ(grammatical inference)ʽԵĹѧϰ.ԵĹѧϰоδԵϢ,ͨƶϵõԵĶ.ѧϰԵնԲͬʽʾʱ,ѧϰҲͬ.ϸ˵,ķƶָѧϰԵĶķʾʱĹѧϰ.
ķƶϴԵϢ(),ͨһƶϹ,յõԵķ().Ϣһһ,ͬʱһ,ܰϢ.ķƶ,׷ݵ2050ĩ,ڼѧĳЩо,ķƶһʷƾõо;ͬʱ,ķƶⱾеĸ,䷢չ,дۺͼҪȥо̽,һ˵о.
ķƶо20,ر19701980,ȡ˷˶оɹ.80ʼ,йķƶоԽԽ,ԭڸоѺܳ;ķƶⱾе,ʹоڵ״̬.,оŽһЩ,Ŵ㷨õķƶ,رǽͳ۽ϵķƶ,ʹķƶϽʵӦóΪ,ķƶϵоֻԾ,1993ٿ4ķƶרĹʻ.һЩרҲķƶϵоɹ,ȼƶϡ㷨ѧϰۺͼѧϰ,,ACMڼ۵ȻҲ.
ĿǰΪֹ,ڻ漰ķƶҪУ14.ּڽķƶϵģͺͷ,رܵǰоȵ.ڽоɹʱرгй޹ķƽķķĳࣩԼķƶϷ.
1 йض
һ޹ķ(context-free grammar,CFG)GһԪʾ,
G=(N,,P,X)
NֱͦΪռϺռ;PΪʽ;XΪʼռ.ĸV=NȦ.ϴϣմΪ*,մæűʾ.+=*-{}.VϵռͷռɵļϣţΪV*,V+=V*-{}.һĳȼΪ||.PÿʽA,,AN,¡V*.æ±ʾ,,,A=A,=æǦAһʽ.±ʾ0,1,...,m(m0)
=01...m=.
,Ц0,...,mΪӦµһƵ.ķGԼΪL(G),
L(G)={s|sʦ*},Xs},
ҲǶL(G)һʵs,ڴXsһƵ,Ƶ̿һʾ,ͳΪGs﷨,ĸΪʼռX,ҶΪs.״ڲıǣΪs(skeleton).ƵҲʹõĲʽбʾ,һʵsƵ̼ΪD(s)=(r1,...,rm),riΪPвʽ.
һCFG GĲʽPевʽ:AaAaB,A,BN,aʦ,GΪķ(regular grammar).һL,ҽһķG,L=L(G).ͬʱ,һL,ҽһȷ״̬Զ(deterministic finite automata,DFA)A,L(A)=L.,ķԺDFAʿɻ滻.
һL,ռsL,sΪL;sL,sΪLķ.LS+L޸ɵļ;LķS-L޸ɵļ.
һЩCFķĶ.
(1) Gķ(linear grammar)ҽʽ:AuBv,Au,A,BN,u,vʦ.Gżķ(even linear grammar,ELG)ҽGķ,AuBvĲʽ:|u|=|v|.
(2) GǼȷķ(simple deterministic grammar)ҽʽ:Aa,aʦ,N*,||2;ͬʱ,AaAa¡P,Ц=.
(3) GǼķ(very simple)ҽGΪGreibachʽķ,Ҷÿռaʦ,PһAaV*Ĳʽ.ǼȷӼ.
гֵʽйظĶͽһͼοף5.
2 ķƶϵģ
ķƶϵо׷ݵ2050ĩ.Chomsky61957.ϵͳϸسһоGold.1969ף7,ķƶϵľģ,Եļʶģ.
2.1 Եļʶģ
Goldķƶһ:κʱt,ƶ豸ϢԪit,ƶ豸һ²⣨ƶϽH(i1,...,it).H(i1,...,it)ʾϢԪi1,i2,...,itõĲ².ʱ֮,ƶ豸Ĳ²ⲻṩϢԪı,Ҹò²ǹڴѧϰԵȷ,˵ƶ豸ʹõһɹƶ㷨,ҲơԵļʶϡ.i1,i2,...ΪУѵУ.ѧϰΪL,Lʾ(positive presentation)ָһϢԪik(k=1,2,...)ΪL;Lʾ(complete presentation)ָһikΪһԪ(w,b)ʦ*{0,1},b=1,wΪL,wΪLķ.
. Ϊһݹö,ƶ豸IDʾʾмʶָ:LLһʾʾI=i1,i2,...,ʱt,IDit²Ht=H(i1,...,it),Hǿɼ,һʱk,hk=hk+1=...hkǶLȷ.
(Gold). LΪһԣӣ,CFΪ,ʾвܼʶCF{L};ʾпԼʶκοö.
Gold,ֻṩ,Ҳܼʶ.һ˾ɥĽ,һҲܺ:Ϊ,,ṩ,һĳʱt,ƶ豸Ĳ²htǴѧϰLĳ,:htLL,ʱ,²htʼղ,ҲϢƶ豸ȥ².ֳΪַ(overgeneralization).
2.2 ʽѧϰģ
GoldĽʹ˺Ȼ뵽,ṩ,ṩϢ.GoldķϢһַ,ܶೡϷṩ,ҰϢ,Ӵĸԣ8.Angluinһڶʽʱͨʽȷʶ(exact identification using queries in polynomial time)ģͣ9,10.ģаʦѧϰɫ,нʦشѧϰ(ƶϵͳ)Ĺڴѧϰ$L$й,͵:
1.Ա(membership).ƶ豸ṩһӴw,ʦشôǷΪѧϰLĺϷ;
2.ȼ(equivalence).ƶ豸ṩһķG,ʦشķǷȼڴѧϰL.شno,ͬʱṩһw,wL(G)wL,wLwL(G).ȼʵǻشǰƶϽGǷΪս.
Angluinף11ֻ֤ʹõȼ,CF಻ڶʽʱʶ;һ,AngluinKharitonף12֤,ʹóԱ͵ȼ,CFķʶѶͨĽ൱,ĿǰΪֹδҵʽʱ㷨.
2.3 ѧϰģ
,õ㷺ӦõValiantĽѧϰģ(probably approximately correct learning,PAC)13.ڸģ,شӦ*ѡȡ,*ĸʷֲDȷδ֪.ƶϹ̵ĳɹ:ȷԲźĲ.ҲͬΪṩƶ㷨.һɹƶ㷨Ը߸(1-)ѰҵС(Сڦ)ķ.
Valiantĸģ͵õ㷺Ӧ,رʶϢͻ.ЩӦó,ķʾ.һͨķ,ÿʽӦĸ,͵õһķ.һķӦظÿһ,Ӷ˴ϵĸʷֲ.޹ķӦ޹ķ(stochastic CFG,SCFG);״̬ԶӦɷģ(hidden Markov model,HMM).ں½нֱӦЩʾƶ㷨.
3 CFķ༰ƶϷ
˵,ƶ豸ƶʱӹ,²ɺͲ²ѡ.ν²⼴ΪܵƶϽ,CFķƶ˵,һ²һCFķ.в²ɷͳطΪ:öٷ͹취.öٷ14,15ǻһʵ,󲿷ҪķЧؽö.öٷͨǵķеķö,ɴ˹²ռ.ף15ԶķӶȵ˳޹ķö.ķʽChomskyʽGreibachʽķ.ΪЧ,ÿķԤ,Ա⻨ѹʱ䴦Щܱܵķ,ķ:ѴĳķĽṹͬ(ķṹָͬķķս֮ɽӦϵ);Чķ(ķĳһս,޷ս,ѭƵ,X...X,XN)ȵ.ף14ԽṹϵΪƫϵ,ķö.CFG G1G2,ķG1ṹķG2ָG1﷨״G2ӦϵӼ.öٷŵֱۡ(Ϊ䱾пܽ,ԴϿҵŽ);ȱǼ㸴Խϸ,ڽʵ.,öٷķƶϵо,Ĳһ.
취Ƕϵͳķ,ʵĽṹϢ,ķ.ͨöٷ취ɲ²ռ,һڲ²ռн,ƶ豸ڶ²ѡ뵱ǰЭĲ²⣨ŻŲ²⣩.Angluin£2оһЩ.Щ໥֮,ǵ˼붼ǲøֶ,ܿҳŻŲ².ʽǸһϵео,Щͨƶķ,Ӧй.ڴ˷,²ռеĲ²ͨĳƫϵ,ͨ.ķG1ķG2ָͨL(G1)L(G2).,һ²HܰĳЩ,бHͨĲ²Ͳ迼.
ƶϷֻǶԳƶϹ̵ķ,ʵʷв²ɺͲ²ѡ̿ںһ淴.ǽһЩķƶϷ,ҲӦù㷺ҽѶԸķ,޹ķƽ.
3.1 Ȼʵƶ
νȻʵָͨľӴ,ᵽĽṹʵԵ.Solomonoff1959ף16һķƶϷ,˼ǸCFԵġظ,ÿwS+,ȴwɾĳӴõw,ѯwǷΪLʵ;,ٽɾӴظκwеõw,ѯwǷΪLʵ,,ƶϳһݹ.,anbnĴLʵ,Lķаʽ:AaAb.Ȼ,÷S+ѡҪϸ:S+̫С,©ܶҪĵݹ;S+̫,㸴˲;ͬʱ÷ĳЩCFķƶϲ,AaAb|cAd1.ʵ,Solomonoffδϸƶ㷨,̸㷨ʵ,˺оһЩ.
һȻʵƶϵB.KnobeK.Knobeķ17,ʵһϵʽĴӻ,㸴Խϸ.һTanatsuguĹ㷨18,㷨ͷ,CFķƶ,а3:ȴгǶ(self-embedding)ṹ;ȻӸƶϳķ;һķʽķCFķ.ף18Ϊ㷨CF,δ㸴.Ϊ,㷨ö,ʵʷǳSolomonoffķ.
ΪоλȡʽԼԼڹ¹ԼʱθйԼ,һڸõ޹ķƶϷ1921.÷ͬȻʵΪƶϳ,Ҫص:(1) ڽиķƶ(ƶϵԹģϴ)ʱɸ֪;(2) ƶϳķṹȻ.õ˼󽵵ķƶϵĸӶ.
3.2 ӽṹʵƶ
CFķƶĸ,оCFķƶʱ,ṩʵͬʱ,ӶϢ.
Crespi-Reghizziף12нһַ,Ӵŵʵƶķ23.һCFG G,GÿʽA֮A()õķG,GɵʵΪGĴʵ.
ʵаʵϢ.֪,CFG˵,ķṹʵ״,˵,ʵ״ķṹ.,ƶ㷨˵,ЧϢʵ(״)Ϣ.ǰֽϢڵʵΪṹʵ.
֤,һCFG GʵӦɵļϣΪDT(G)һ,νָϿĳԶʶ,ҼʹDT(G)иڲδ־,üͬǺϣ24.ڴ,ӽṹƶCFķ,ԹΪԶʶ.
Angluinף9һЧƶ㷨,ͨȼͳԱʶȷԶ(DFA).Sakakibaraף24ͨAngluinDFAƶ㷨ƹ㵽Զ,Ӷ,ӽṹʵ,CFͨṹԱͽṹȼڶʽʱʶ.
3.3 CFķƶ
CFķƶĸ,о߽עתCFķо,ȡ˿ϲĳɹ.
Ishizakaף25иڼȷķƶ㷨,:ͨȼͳԱ,ȷԿڶʽʱʶ.
Yokomoriף26о˼ȷԵࡪԵѧϰ.ó:Դ,ڶʽʱʶ.
Takadaף27бELG(żķ)ƶԹΪDFAƶ,һʵ̵ֹĶʽʱ㷨.Ϊ,һķƶΪһԼ򵥵ķƶһȻЧķ.ԶTakadaķЩī.
TakadaĻ˼:FΪһĸ,һELG G=(N,,P,X),PÿʽFĸΨһ־.f=f1f2...fkF*,XfGwʾGĿʼռXʼ,ʹñ־Ϊf1,f2,...,fkĲʽ,w.CΪĸFϵһ,ķGڿƼC²ԶΪ:
LC(G)={wʦ*|fGw,fC}.
ǿƼCһӶӦLC(G)һӵ.Takada֤:κһĸϵżL,ɦϵһͨELG G0һƼC²,CΪ.ԦһELL L,
L=LC(G0)={wʦ*|X0fG0w,fC}.
CΪһ,G0ĶΪ:
G0=({X0},,P0,X0)
СP0={X0aX0b|a,bʦ}{X0ab|a,bʦ}{X0a|aʦ}{X0}.
3.4 Ŵ㷨缼ķƶ
90ʼ,ķƶϵо𽥻Ծ,һķƶչֵĺǱڵӦǰ;һǼѧоĽչķƶоע.ǰᵽ,ķƶĸԴӴĲ²ռ,оߺȻؿǵŴ㷨ķƶо29,30;ͬ,ĳЩضķʶϾĳֵȼ۹ϵ,Ƴض͵,ʹṹķһӦϵ,ķƶתΪѧϰ31,32.
3.4.1 Ŵʽķƶ
Ŵ㷨ģ̵ļģ,Ҫص:һϵͳ澺ʤ̭ԭ;һ֪ʶµ.Ŵ㷨ΪһµȫŻ㷨, ͨá³ǿڲдص,㷺.һŴ㷨Ҫ:(1) ;(2) ʼȺ趨;(3) ӦȺ;(4) Ŵ;(5) Ʋ趨.CFķƶŴʽ㷨(GIGA)ͬ5Ҫ.
νָռн⣨ֳƸ壩ı.CFķƶĽһCFķ,,GIGAеıķıʾ.֪,ͬһCFԿòͬʽCFķʾ.ʽ,ÿA,V*.Ԧĸʽͬ,ͻõͬķʽ.ʹý϶Chomskyʽ,ÿʽABCAa,A,B,CN,aʦ.ȷķʽ,ķĽһ·Ϊ.һֱӱ,ÿвʽһõַʾ;һǼӱ,һĹ,ʽתΪͼݹת01.
Ŵ㷨ȺͲҪ,ΪŴ׼һɿܽɵĳʼȺ.ͨGIGAгʼȺĶ,ÿ·õ:ȷֱٶռϦͷռN,ڦNkʽ,Ȼÿʽϱ׶ѡķʽʽ,kڻĿķеĲʽ,Ҫ󦲡NֱȼĿķռϺͷռ.
ӦȺڽ.GIGAӦȺһ壨һCFķЭ̶,ҲǴӶĽͶԷľܾۺ.
Ŵһӽ(crossover)ͱ(mutation).GIGAӽһǽʽҲĳλõķţռռн;ǽĳʽҲĳλõķ(ռռ滻ɱķ(ռռ).
Ʋ趨趨ȺСÿĸԼӵǰһĸʱ,ǰиֱӽĸ.
,ǿԿŴʽķƶϷص:(1) ƶϵĳͷ;(2) Ԥ֪ȡķһЩ,ʽռϺͷռ;(3) ȡķһĳַʽ.
3.4.2 缼ķƶ
(neural networks)ǽ˹ܵһǰо.ص:ģнṹ;Ϣķֲ洢Ͳд;õӦԡ֯Ժݴ;ǿѧϰ䡢롢ʶ.
ĿǰΪֹ,缼޹ѧϰ׽,Խ϶Եѧϰ.RNN(recurrent neural network)Զϸ˵ķ32ݣʶϾĳֵȼ۹ϵ33,ԵѧϰתΪѵRNN31,32.ķƶϵĵ:ͨͷѵõΪ,жһǷ.ķƶϵһ,ĽṹӦķṹ,,ͨѧϰõתӦķ34.
4 ķƶ
ķƶоķƶ.ƵĸԴһڴͳȷƶģͺͷķ;һģͺͷڵӹ̵ĺܶЧӦ.ķͨķĻϼ˸ģ.ķƶϹ̵ʵԸʹΪֶμٽṹƶϹ,ĳ֡ʡ²Ŀ,Դ˼ٲ²ռ,Ӷͼ㸴.ġʡǵͨķĸ(Feldmanף35иķԵһʽ)ķ֮Ǻϳ̶.
Horning䲩ʿһöٷӸ(ÿһ)ʶSCFG36.˼пܵĲ²,öġʡȡ.Ƶķף15ݺף37ᵽķ.Ȼ,öٷе,ЩЧʺܵ.
һSCFGƶϷCookĵɽ38.ȶһֺӶȵķ,ڴ˻϶ķĸӶ.ƶϵĴ¹:ȴӸһʼķ(ķĸӶȽϸ),Ȼһϵ(滻ظֵĴ)Գʼķ,ֱķ޷,ջһӶ͵ķ.˷,Stolckeˣ39һģͺϲ,:ȴӸʼķ;Ȼͨģͺϲ(ϲHMMе״̬ϲSCFGеķռ)ķƹ.ǷϲԼʱֹͣϲķǺϳ̶Ⱦ.
ϷĹͬصǲķṹƶ.оظʲĹ,ķṹƶϹ̴֮ԸʲĹƹ.ԭ,ĿǰڸʲĹ㷨Ҫ:HMMǰ-㷨(forward-backward,F-B)40ݺSCFG-㷨(inside-outside,I-O)41.HMMΪ,ӳʼHMM(һ״̬ȫHMM)ʼ,F-B㷨иʹ,ʹﵽֲ;ɾȥΪ0ʺС״̬ת,ӶõHMMĽṹ.ֱHMMSCFGĲƹ.
4.1 HMM
һHMM һԪ鶨,=(S,,T,O,),SΪ״̬,Ϊĸ,TΪ״̬תʷֲ,OΪĸʷֲ,Ϊʼ״̬ʷֲ.:S={s1,...,sn},siΪе״̬;T={tij}|1i,jn},tijΪ״̬qiתqjĸ,ǰʱt=1,2,3,...״̬תϵ,tʱ״̬Ϊqt,tij=Pr(qt=sj|qt-1=si);O={oj(a)|1jn,aʦ},oj(a)Ϊ״̬qjʱĸaĸ;={i|1in},iΪ״̬qiǿʼ״̬ĸ.
HMMĲƿɹΪ3(赱ǰHMMΪ):һw,
1.wĸPr(w|);
2.Ѱ·s=qi1,...,qilʹPr(s|w,),Pr(s|w,)ʾw˽ʱ·Ϊsĸ;
3.Ʀ˵Ĳ(T,Oͦ),ʹPr(w|).
ö̬̼Чؽ.н2Ч㷨Viterbi㷨42;3ĽF-B㷨,õFB(w=a1...aT):FFk(si)ΪFk(si)=Pr(a1...ak,si|),ʱk(ʱַֹΪwǰ׺a1...ak)ʱ״̬Ϊsiĸ;BBk(si)=Pr(ak+1...aT|si,),˴״̬siʼw׺ak+1...aTĸ.1ĽõF,Ϊ:
(1) ʼ:
F1(si)=ioi(a1) 1in;
(2)
Fk+1(sj)=(Fk(si)tij)oj(ak+1) ,1jn;
(3)ֹ
Pr(w|)=FT(si).
F-B㷨һֵ(expectation maximization,EM)ڽ֮ǰ,ȶʦt(i,j),ڦ˽wĹ,tʱ״̬Ϊsit+1ʱ״̬Ϊsiĸ.
t(i,j)=Pr(qt=si,qt+1=sj|w,).
t(i)ʾڦ˽wĹtʱ״̬Ϊsiĸ,
t(i)=t(i,j).
F-B㷨3ĹΪ:
(1) oldΪʼģ.
(2) ݵǰold͸w,
 ״̬si,sj,㲢ænewеtijֵΪ:

 ÿ״̬sjַa,㲢ænewoj(a)ֵΪ:

(3) ænew滻old,ظ(2)ֱold޴仯.
Baumˣ43֤:(1) ʼoldģ(ֵ),(2)ĽǦold=new;(2),newȦoldԴ,Pr(w|newPr(w|old).
4.2 ޹ķ
һSCFG GƿΪһCFGһq,G=(G,q),,G=(N,,P,X)һCFG,qһq:P0,1
AN,q(A)=1.
ھs,ӦһƵD(s)=(r1,...,rm)(riP)ĸΪ
Pr(s,D(s)|G)=q(r1)...q(rm).
Ԧ*ϵһw,wGܵĸΪ

Pr(w|G)(wʦ*)ɦ*ϵĸʷֲ.
SCFGĲͬHMM3:
(1) һw,SCFG GĸPr(w|G);
(2) ѰGƹwܵ;
(3) (Gq),ʹPr(w|G).
ǰCKYEarleyƵĶ̷̬.3ı׼-(inside-outside,I-O)㷨.IOֱΪ(w=a1...a|w|):
I(i,j,A)=Pr(Aai...aj|G) AN,1ij|w|,
O(i,j,A)=Pr(Sa1...ai-1Aaj+1...a|w||G) ,
5 ķƶϵӦ
ķƶоĶ֮һ,ѧϰȻԵģ,ܺо߶ܷﵽһĿıʾ.ʵ,ķƶϵҪӦǽṹģʽʶ(structural pattern recognition),Щ,ĳЩضģʽһķ,ֹЩķǳ,ҪԶ򲿷ԶЩķ.Crespi-ReghizziķƶϽг﷨ƣ45.
,ԽԽķƶ㷨ĳ,ķƶϵӦԽԽ㷺.ҪϢȻԴݲɼ֪ʶȡ.һЩоֱķƶϸķ4648.
6 ķƶϵо
ĽķƶϵģͺƶϷ,رʾΪ޹ķࡢ޹ķɷģ͵ƶϷ.ǿ԰ķƶϵоɹΪ:۷ķƶϳ̵о,Խķƶģ,ͼѰضĳģ,ķƶϵĿɼԺͼ㸴ԵĴ;ʵѰЧеķƶϷ,ŽЩڽʵ.ķƶоķչ̿ɹΪ:ķƶ(˿,ƶ㷨һں,˵ȫԶ,ƶϹ˵Ĳ),ģ(ʱ˶ƶϹ̵ĸԤ,󽵵ͼ㸴),ٵģ(ͶƶϽҪ,ԽƽŽϿ).
˵,ĿǰΪֹ,Ȼķƶϵоȡ˺ܴĽչ,Ϊһо,Զ,һЩдͳһ.оķƶϳ̺ģ͵о;ĳʵضķ,Ȼĳģ±Чƶϣʶϣ,ƶܱԼΪĳЩķࣨķ,ķ49)ƶ,ʵӦûƵķ;һЩо߿ǸӸϢʵĽṹϢ,ͬʵӦû,ЩϢṩ.
,ķƶչֵĺǱڵӦ,ἤо߳ԴµĽǶȻµķѰʵʿõķƶϷ.ر,żѧѧƺķչ,о߻᳢ԽһЩۺ¼õķƶ,罫Ŵ㷨ķƶϾǵ͵.ͬʱΪ,ģͺͷΪо.˵,ķƶϵоһҸսԵĹ.
л ĹڶԺʿָɵ.жƪҪФ,ڴ˱ʾĸл.
עоõȻѧ𡢹863߿ƼĿ͹ҡ塱ƼĿ.
ͨѶϵ:룬 100080,йѧԺоѧоʵ
߼飺,1969,ʿ,ҪоΪʽԼ,ѧϰ.
ߵλйѧԺоѧоʵҡ 100080
E-mail: zrl@ox.ios.ac.cn
ο
1 Fu K S, Booth T R. Grammatical inference: introduction and servey(Part 1, Part 2). IEEE Transactions on Systems, Man and Cybernetics, 1975,SMC-5(1):95111;1975,SMC-5(4):409423
2 Angluin D, Smith C H. Inductive inference: theory and methods. Computing Surveys, 1983,15(3):237269
3 Miclet L. Grammatical inference. In: Bunke H, Sanfeliu A eds. Syntactic and Structural Pattern RecognitionTheory and Applications. World Scientific, 1986. 237290
4 Sakakibara Y. Grammatical inference: an old and new paradigm. Lecture Notes in Artificial Intelligence 997, 1995. 124
5 Solomaa A. Formal Languages. London: Academic Press, 1973
6 Chomsky N. Syntactic Structures. The Hague: Mouton and Co., 1957
7 Gold E M. Language identification in the limit. Information and Control, 1967,10(5):447474
8 Gold E M. Complexity of automaton identification from given data. Information and Control, 1978,37(4):302320
9 Angluin D. Learning regular sets from queries and counter-examples. Information and Computation, 1987,75(1):87106
10 Angluin D. Queries and concept learning. Machine Learning, 1988,2(3):319342
11 Angluin D. Negative results for equivalence queries. Machine Learning}, 1990,5:121150
12 Angluin D, Kharitonov M. When won't membership queries help? In: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing. ACM Press, 1991. 444454
13 Valiant L G. A theory of learnable. Communications of the ACM, 1984,27:11341142
14 Giordano J Y. Inference of context-free grammars by enumeration: structural containment as an ordering bias. LNAI 862, 1994. 212221
15 Wharton R M. Grammar enumeration and inference. Information and Control, 1977,33(3):253272
16 Solomonoff R J. A new method for discovering the grammars of phrase structure languages. Information Processing, New York: UNESCO, 1959. 285290
17 Knobe B, Knobe K. A method for inferring context-free grammars. Information and Control, 1976,31(2):129146
18 Tanatsugu K. A grammatical inference for context-free languages based on self-embedding. Bulletin of Informatics and Cybernetics, 1987,22(2):149163
19 .ȡ޹ķһֽʽ㷨.ѧ,1996,19(3):168173
(Dong Yun-mei. An interactive algorithm for acquisition of context-free grammars. Chinese Journal of Computers, 1996,19(3):169173)
20 .ڸõ޹ķƶ.ѧ,1996,7(863ר),178181
(Dong Yun-mei. Context-free grammatical inference based on reusing. Journal of Software, 1996,7(863 special issue):178181)
21 .һ޹ķȡ̵ƺʵ.ѧ,1998,9(8):601605
(Zhang Rui-ling. Design and implementation of a procedure for acquisition of context-free grammars. Journal of Software, 1998,9(8):601605
22 Crespi-Reghizzi S. An effective model for grammar inference. In: Gilchrist B ed. Information Processing 71, New York: Elsevier North-holland, 1972. 524529
23 Aho A V, Sethi R, Ullman J D. Compilers: Principles, Techniques and Tools. MA, Reading: Addison-Wesley, 1986
24 Sakakibara Y. Learning context-free grammars from structural data in polynomial time. Theoretical Computer Science, 1990,76(2):223242
25 Ishizaka H. Polynomial time learnability of simple deterministic languages. Machine Learning, 1990,5(2):151164
26 Yokomori T. Polynomial-time learning of very simple grammars from positive data. In: Proceedings of the 4th Workshop on Computational Learning Theory(COLT'91). Morgan Kaufmann, 1991. 213227
27 Takada Y. Grammatical inference for even linear languages based on control sets. Information Processing Letters, 1988,28(4):193199
28 Sempere J M, Garcia P. A characterization of even linear languages and its application to the learning problem. LNAI 862, 1994. 3844
29 Dupont P. Regular grammatical inference from positive and negative samples by genetic search: the GIG method. LNAI 862, 1994. 236245
30 Wyard P. Representational issues for context-free grammar induction using genetic algorithms. LNAI 862, 1994. 222235
31 Alquezar R, Sanfeliu A. A hybrid connectionist-symbolic approach to regular grammatical inference based on neural learning and hierarchical clustering. In: Carrasco R C, Oncina J eds. LNAI 862, Berlin: Springer-Verlag, 1994. 203211
32 Carrasco R C, Forcada M L, Santamaria L. Inferring stochastic regular grammars with recurrent neural networks. In: Miclet L, de La Higuera C eds. LNAI 1147, Berlin: Springer-Verlag, 1997. 274281
33 Cleermans A, Servan-Schreiber D, McClelland J L. Finite-state automata and simple recurrent networks. Neural Computation 1, 1989. 372381
34 Roques M. Dynamic grammatical representations in guided propagation networks. LNAI 862, 1994. 189202
35 Feldman J. Grammatical inference and complexity. Information and Control, 1972,2(3):244262
36 Horning J J. A study of grammatical inference Ph.D. Thesis. Stanford University, August 1969
37 Van der Mude A, Walker A. On the inference of stochastic regular grammars. Information and Control, 1978,2(5):310329
38 Cook C M et al. Grammatical inference by hill-climbing. Information Sciences, 1976,2(1):5980
39 Stolcke A, Omohundro S. Inducing probabilistic grammars by Bayesian model merging. LNAI 862, 1994. 106118
40 Rabiner L R. A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of IEEE, 1989,77(2):257286
41 Lari K, Young S J. The estimation of stochastic context-free grammars using the inside-outside algorithm. Computer Speech and Language, 1990,4(1):3556
42 Viterbi A J. Error bounds for convolutional codes and anasymptotically optimal decoding algorithm. IEEE Transactions on Information Theory, 1967,IT-13(2):260269
43 Baum L E, Sell G R. Growth functions for transformations on manifolds. Pacific Journal of Mathematics, 1968,27(2):211227
44 Sakakibara Y et al. Stochastic context-free grammars for tRNA modeling. Nucleic Acids Research, 1994,22(1):51125120
45 Crespi-Reghizzi S, Melkanoff M A, Lichten L. The use of grammatical inference for designing programming language. Journal of the ACM, 1973,16(2):8390
46 Young S J, Shih H H. Computer assisted grammar construction. LNAI 862, 1994. 282290
47 Dong Yun-mei. Collection of SAQ Report no.17. Technical Report no. ISCAS-LCS-95-09, Laboratory of Computer Science, Institute of Software, The Chinese Academy of Sciences, Beijing, August 1995
48 DONG Yun-mei et al. Collection of SAQ Report no.816. Technical Report no. ISCAS-LCS-96-1, Laboratory of Computer Science, Institute of Software, The Chinese Academy of Sciences, Beijing, March 1996
49 Angluin D. Inference of reversible languages. Journal of the ACM, 1982,29(3):741765
1998-09-29յԭ,1999-03-15յ޸ĸ
