An Efficient Technique for Conversion of Regular Expression to and from Finite Automata

Authors

  • Neha Sharma South Point Institute of Technology and Management, Sonepat

Keywords:

Algebraic method, partition, expression, alternative, research

Abstract

Regular expressions are used to represent certain set of string in algebraic manner. Regular expressions are widely used in the field of compiler design, text editor, search for an email- address, grep filter of unix, train track switches, pattern matching ,context switching and in many areas of computer science. The demand of converting regular expression into finite automata and vice versa motivates research into some alternative so that time taken for above is minimized. For conversion of deterministic finite automata to regular expression, several techniques like Transitive closure method, Brzozowski Algebraic method and state elimination method have been proposed. In this paper, for Conversion of regular expression to NFA we study the Thomson Algorithm; to convert NFA to DFA we use Subset Construction method, to minimized DFA constructed from previous step we use partition method and finally to convert DFA back to RE we use Universal Technique.

References

Alfred V. Aho, ―Constructing a Regular Expression from a DFA‖, Lecture notes in Computer Science Theory, September 27, 2010, Available at http://www.cs.columbia.edu/~aho/cs3261/lectures.

Ding-Shu Du and Ker-I Ko, ―Problem Solving in Automata, Languages, and Complexity‖, John Wiley & Sons, New York, NY, 2001.

Gelade, W., Neven, F., ―Succinctness of the complement and intersection of regular expressions‖, Symposium on Theoretical Aspects of Computer Science. Dagstuhl Seminar Proceedings, vol. 08001, pages 325–336. IBFI (2008). [4] Gruber H. and Gulan, S. (2009), ―Simplifying regular expressions: A quantitative perspective‖, IFIG Research Report 0904.

Gruber H. and Holzer, M., ‖Provably shorter regular expressions from deterministic finite automata‖, LNCS, vol. 5257, pages 383–395. Springer, Heidelberg (2008).

Gulan, S. and Fernau H., ―Local elimination-strategies in automata for shorter regular expressions‖, In Proceedings of SOFSEM 2008, pages 46–57 (2008).

H. Gruber and M. Holzer, ―Finite automata, digraph connectivity, and regular expression size‖, In Proceedings of the 35th International Colloquium on Automata, Languages and Programming, Iceland, July 2008. Springer.

Downloads

Published

30-09-2016

How to Cite

Neha Sharma. (2016). An Efficient Technique for Conversion of Regular Expression to and from Finite Automata. International Journal for Research Publication and Seminar, 7(5), 42–47. Retrieved from https://jrps.shodhsagar.com/index.php/j/article/view/865

Issue

Vol. 7 No. 5 (2016): July - Sept 2016

Section

Original Research Article

License

Copyright (c) 2016 International Journal for Research Publication and Seminar

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Re-users must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use. This license allows for redistribution, commercial and non-commercial, as long as the original work is properly credited.