The Equivalent Conversion between Regular Grammar and Finite Automata

Affiliation(s)

Department of Information Technology, Yingtan Vocational and Technical College, Yingtan, China.

School of Information Tech- nology, Jiangxi University of Finance and Economics, Nanchang, China..

Department of Information Technology, Yingtan Vocational and Technical College, Yingtan, China.

School of Information Tech- nology, Jiangxi University of Finance and Economics, Nanchang, China..

ABSTRACT

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.

Cite this paper

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.

J. Zhang and Z. Qian, "The Equivalent Conversion between Regular Grammar and Finite Automata,"

References

[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.

[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.