论文关键词：Regular Grammar；识别；自动机
　
　　论文摘要：RG是形式语言中最典型的一类文法。主要讨论和分析了RG的一种识别分析方法，给出了该方法的主要算法及实现的关键技术。对文法识别和自动机生成有决定性的作用。可给后续研究提供支持。
　　
　　　　Research of the Key Technologies of RG Identifying
　　SHI Hai-feng1, SHI Jing2
　　(1.Jiangsu Polytechnic University,Changzhou 213164,China;2.Changzhou College of Information Technical,Changzhou 213164,China)
　　Abstract: Regular Grammar is one of the most typical grammar in Formal Language. Discussed a method to identify the RG,and gave the main algorithms to achieve the key technology,It plays a decisive role in recognition of grammar and the generation of automatic. And Can provide support to the follow-up study.
　　Key words:regular grammar;identify; automatic
　　
　　1 引言
　　
　　乔姆斯基把文法分成四种类型，即0型、1型、2型和3型。这几类文法的差别在于对产生式施加不同的限制。设G=(VN，VT，P，信捷职称论文写作发表网，S)，若P中的每一个产生式的形式都是A→Ba或A→a，其中A和B都是非终结符，a是终结符，则G是3型文法或正规文法，即RG.RG又有左线性和右线性之分，即右部为“Ba”则为左线性，为“aB”则为右线性，本文仅以左线性情形，右线性情形就不赘述。
　　本文是在设计了一个识别输入文法是否为RG的软件的基础上，着重对基本原理和关键技术做研究和分析，给出了一种识别方法的原理，在更好的加深巩固形式语言这一重要理论的同时，使得该理论更紧密的与实践相联系。
　　
　　2 相关定义及理论
　　
　　定义2.1文法与自动机等价
　　根据形式语言理论，三型文法产生的语言是有穷自动机(FA)所接受的串集合。可以给出3型文法和相应识别系统FA间的转换规则。
　　采用下面的规则可从正规文法G（假定G为右线性文法）直接构造一个有穷自动机NFA M；使得L(M)=L(G)：?
　　① 字母表与G的终结符集相同；
　　② 为G中的每个非终结符生成M的一个状态，(不妨取成相同的名字)G的开始符号S 是开始状态S；
　　③ 增加一个新状态Z，做为NFA的终态；
　　④ 对G中的形如 A→tB其中t为终结符或ε，A和B为非终结符的产生式，构造M的一个转换函数f(A,t)=B；
　　⑤ 对G中形如A→t的产生式，构造M的一个转换函数f(A,t)=Z。
　　定义2.2 NFA的确定化
　　在有穷自动机的理论里，有这样的定理：设L为一个由不确定的有穷自动机接受的集合，则存在一个接受L的确定的有穷自动机。将NFA转换成接受同样语言的DFA的算法称为子集法。详细证明可查阅参考文献[1]。