Here is the construction algorithm from regular grammar to finite automata, and the proof of correctness. For each right linear grammar G R (or left linear grammar G L), there is one finite automata M where. The following theorems are concerned about the equivalence between regular grammar and finite automata. If a regular grammar G describes the same language as that a finite automata M identifies, viz.,, then G is equivalent to M. For some set ω where, if where holds, then we say that DFA can accept the condition set ω.ĭefinition 2. That is to say, if the condition is ε, the current state is unchanged if the state is s and the condition aw, the system will first map δ(s, a) to s 1, then continue to map from s 1 until the last one. Now, we extend the definition domain of δ to meaning that for any, and, and hold. With δ, one can easily identify whether the condition in can be accepted by DFA or not. A DFA M is an automatic recognition device that is a quintuple denoted by, where each element in S indicates one state in present system ∑ denotes the set of conditions under which the system may happen δ is a single valued function from to S with indicating if the state of the current system is s 1 with an input a, there will be a transition from the current state to the successive one named s 2 s 0 is the very unique start state and F the set of final states. The definition of NFA and regular grammar as well as the subset-based construction algorithm from NFA to DFA can be easily found in. The definition of DFA where some notations in the remainder of this paper are shown is given first. Some Equivalent Conversion Algorithms between Regular Grammar and Finite Automata As far as language representation is concerned, the equivalence exists between the language regular grammar G describes and that finite automata M identifies.Ģ. A finite automata M including NFA (Non-deterministic Finite Automata) and DFA (Deterministic Finite Automata), applied to the formal model representation and research on digital computer, image recognition, information coding and neural process etc., is the formal model of discrete and dynamic system that have finite memory, and is applied to word identification and the model representation and realization of generation process during the course of word analysis in compiler. All these are just a simple introduction to grammar, and automata theory, which plays an important role in compiling theory and technology, has another far-reaching impact on computer science.Ī regular grammar G, applied to formal representation and theoretical research on regular language, is the formal description of regular language, mainly describes symbolic letters and often identifies words in compiler. Chomsky’s Conversion Generative Grammar was classified into phase grammar, context-sensitive grammar, context-free grammar and linear grammar (or regular grammar) that includes left linear grammar and right linear grammar. Additionally, a relevant example is expounded.Ī rapid development in formal languages has made a profound influence on computer science, especially played a greater role in the design of programming languages, compiling theory and computational complexity since formal language system was established by Chomsky in 1956. And the construction algorithm 5 of the equivalent conversion from finite automata to left linear grammar is presented as well as its correctness proof. The simplified forms of the algorithms and their proofs are given. Some complicated conversion algorithms have also been in existence. The equivalence exists between regular grammar and finite automata in accepting languages. Keywords: Regular Grammar Finite Automata NFA DFA 1Department of Information Technology, Yingtan Vocational and Technical College, Yingtan, China 2School of Information Technology, Jiangxi University of Finance and Economics, Nanchang, China.Įmail: November 21 st, 2012 revised December 20 th, 2012 accepted December 31 st, 2012