The Equivalent Conversion between Regular Grammar and Finite Automata

DOI: 10.4236/jsea.2013.61005   PDF   HTML     11,463 Downloads   19,563 Views   Citations


The equivalence exists between regular grammar and finite automata in accepting languages. Some complicated conversion algorithms have also been in existence. The simplified forms of the algorithms and their proofs are given. And the construction algorithm 5 of the equivalent conversion from finite automata to left linear grammar is presented as well as its correctness proof. Additionally, a relevant example is expounded.

Share and Cite:

J. Zhang and Z. Qian, "The Equivalent Conversion between Regular Grammar and Finite Automata," Journal of Software Engineering and Applications, Vol. 6 No. 1, 2013, pp. 33-37. doi: 10.4236/jsea.2013.61005.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] H. W. Chen, C. L. Liu, Q. P. Tang, K. J. Zhao and Y. Liu, “Programming Language: Compiling Principle,” 3rd Edition, National Defense Industry Press, Beijing, 2009, pp. 51-53.
[2] A. V. Aho, M. S. Lam, R. Sethi and J. D. Ullman, “Compilers: Principles, Techniques, and Tools,” 2nd Edition, Addison-Wesley, New York, 2007.
[3] J. E. Hopcroft, R. Motwani and J. D. Ullman, “Introduction to Automata Theory, Languages, and Computation,” Addison-Wesley, New York, 2007.
[4] P. Linz, “An Introduction to Formal Languages and Automata,” 5th Edition, Jones and Bartlett Publishers, Inc., Burlington, 2011.
[5] R. E. Stearns and H. B. Hunt III, “On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata,” SIAM Journal on Computing, Vol. 14, No. 3, 1985, pp. 598-611. doi:10.1137/0214044
[6] V. Laurikari, “NFAs with Tagged Transitions, Their Conversion to Deterministic Automata and Application to Regular Expressions,” Proceedings of the 7th International Symposium on String Processing Information Retrieval, IEEE CS Press, New York, 2000, pp. 181-187.
[7] C. Allauzen, M. Mohri and B. Roark, “A General Weighted Grammar Library,” Implementation and Application of Automata, LNCS 3317, 2005, pp. 23-34. doi:10.1007/978-3-540-30500-2_3
[8] H.B. Hunt III, “Observations on the Complexity of Regular Expression Problems,” Journal of Computer and System Sciences, Vol. 19, No. 3, 1979, pp. 222-236. doi:10.1016/0022-0000(79)90002-3
[9] A. Brüggemann-Klein, “Regular Expressions into Finite Automata,” Theoretical Computer Science, Vol. 120, No. 2, 1993, pp. 197-213. doi:10.1016/0304-3975(93)90287-4
[10] X. H. Guo, “Grammar Theory Based on Lattice-ordered Monoid,” Fuzzy Sets and Systems, Vol. 160, No. 8, 2009, pp. 1152-1161. doi:10.1016/j.fss.2008.07.009
[11] N. A. Zafar and F. Alsaade, “Syntax-Tree Regular Expression Based DFA Formal Construction,” Intelligent Information Management, Vol. 4, No. 4, 2012, pp. 138-146. doi:10.4236/iim.2012.44021
[12] S. Bhargava and G. N. Purohit, “Construction of a Minimal Deterministic Finite Automaton from a Regular Expression,” International Journal of Computer Applications, Vol. 15, No. 4, 2011, pp. 16-27.

comments powered by Disqus

Copyright © 2020 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.