舆论摘要：格值文法及其谈话

　　正文接洽的重要实质是格值文法及其谈话．李永明熏陶在文[19]中创造了一个新的朦胧自效果模子，即格值自效果，在一个比往常接洽的朦胧自效果更广的框架一格半群意旨下，来接洽自效果表面．文[19]中仍旧表明对于格值谈话，不决定型格值自效果（LA）比决定型格值自效果（DLA）辨别谈话的本领更强，而且从档次构造上去讲，格值自效果比普遍朦胧自效果能辨别更普遍的朦胧谈话．而在典范自效果与普遍朦胧自效果表面中，有一个要害的论断即是文法天生的谈话与自效果辨别的谈话等价．既是在格半群意旨下DlA与lA不等价，咱们天然关怀的题目即是DLA与LA辨别的谈话辨别不妨用还好吗的文法来刻划．从这个题目动身，正文重要商量了格值正则文法的构造，格值自效果与格值正则文法的等价联系，格值正则谈话的本质，格值左右文无干文法及其谈话的本质等题目． 　　正文共分四章，第一章重要回忆了典范自效果与情势谈话的关系常识，囊括典范有限自效果的设置，文法的设置与分门别类以及典范自效果表面中几个要害论断． 　　第二章：在自效果表面中，鉴于格半群，引入格值自效果及其辨别的谈话的设置，格值正则文法及其爆发的谈话的设置，给特殊值正则文法的分门别类，找到了用格值正则文法刻划决定型格值自效果的情势。重要得出如次论断：　　（1）格值正则文法与格值自效果等价； 　　（2）决定格值正则文法与决定型格值自效果等价． 　　第三章：在格值文法的框架下从新给出了格值正则谈话的百般演算对应的文法的结构，从文法的观点来接洽谈话的本质，计划了格值正则谈话对于正则演算的封锁性及其前提．重要得出如次论断： 　　（1）格值正则谈话在并，贯穿，K1eene闭包和数乘演算下封锁； 　　（2）格值正则谈话对于广义走运算，回转演算封锁的充要前提是·演算满意调换律． 　　（3）决定格值正则谈话在并，交，广义交，贯穿，回转及数乘演算下封锁． 　　（4）决定格值正则文法与格值正则文法等价的充要前提是由格L的大肆有限子集Lˉ1，天生的（L，·，V）的子代数是有限的． 　　第四章：连接在格半群意旨下，引见格值左右文无干文法，给出了将格值左右文无干文法辨别变换成与其等价的Chomsky范式文法和Greibach范式文法的算法，结果计划了格值下文无干谈话的本质．