形式语言与自动机理论若干问题研究new

《形式语言与自动机理论若干问题研究new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、电子科技大学博士学位论文形式语言与自动机理论若干问题研究姓名：陈文宇申请学位级别：博士专业：计算机应用技术指导教师：孙世新20091125摘要计算理论是研究使用计算机解决计算问题的数学理论。有三个核心领域：形式语言与自动机理论、可计算性理论和计算的复杂性理论。可计算性理论的中心问题是建立计算的数学模型，进而研究哪些是可计算的，哪些是不可计算的。计算的复杂性理论研究算法的时间复杂性和空间复杂性。在可计算性理论中，将问题分成可计算的和不可计算的；在复杂性理论中，目标是把可计算的问题分成简单的和复杂的。形式语言与自动机理论论述计算的数学模型的定义和性质，这些模型在计算

2、机科学的若干应用领域中起着重要作用，其应用范围已被扩展到生物工程、自动控制系统、图像处理与模式别等许多领域。本文主要研究形式语言与自动机理论中的形式语言理论、自动机理论和形式语言与自动机之间等价性理论的若干问题。研究内容包括：(1)形式语言与自动机理论中关于空串￡的一些问题。(2)四类语言对联合、连接、克林闭包运算的有效封闭性问题。(3)根据等价类构造一类有限状态自动机的方法。(4)通用图灵机的统一、合理的编码系统。(5)一种新的图灵机构造技术：扫描子串技术。(6)非负整数的k元函数对于关系运算和算术运算的图灵可计算问题。(7)非负二进制整数关于关系运算和算术运

3、算的图灵可计算问题。关键词：形式语言，自动机，有效封闭性，扫描子串技术，图灵可计算性ABSTRACTABSTRACTComputationtheoryisthemathematictheoryforsolvingcomputationalproblemswithcomputers．Thethreemainresearchareasofthetheoryare：formallanguageandautomatatheory,computabilitytheoryandthecomputingcomplexitytheory．Thecoreissueofthecom

4、putabilitytheoryistoestablishmathematicmodelofthecomputationandthendecideitscomputability．Thecomputingcomplexitytheorydiscussesthetimecomplexityandthespacecomplexityofthealgorithms．Theobjectiveofthecomplexitytheoryistogroupthecomputableproblemsintosimpleproblemsandcomplexones．Formall

5、anguageandautomatatheorydiscussesthedefinitionandpropertiesofthecomputationalmodels．Thesemodelsplayasignificantroleinmanyfieldsofcomputerscienceandtherangeofapplicationhasbeenextendedtomultiplefieldslikebioengineering，automaticcontrolsystem，imageprocessingandpatternrecognition．Thedis

6、sertationdiscussesformallanguagetheory,automatatheoryandtheequivalencyofformallanguageandautomata．Researchareainchdes：(1)Issuesregardingblankstring￡offormallanguageandautomatatheory．(2)Theeffectivecloserissueoffourtypesoflanguagesbyjoin,linkageandKleeneclosureoperations．(3)Themethodo

7、fcreatingaspecifictypeoffinitestateautomatabyequivalenceclass．(4)TheuniversalreasonablecodingsystemforTuringmachines．(5)AnewtechniquetoereateTuringmachines：substringscantechnique．(6)TheTuringcomputableissueofk-variablefunctionsofnon-negativeintegersbyrelationaloperationsandarithmetic

8、operations．(