CFP last date
22 April 2024
Reseach Article

Construction of a Minimal Deterministic Finite Automaton from a Regular Expression

by Sanjay Bhargava, G. N. Purohit
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 15 - Number 4
Year of Publication: 2011
Authors: Sanjay Bhargava, G. N. Purohit
10.5120/1938-2589

Sanjay Bhargava, G. N. Purohit . Construction of a Minimal Deterministic Finite Automaton from a Regular Expression. International Journal of Computer Applications. 15, 4 ( February 2011), 16-27. DOI=10.5120/1938-2589

@article{ 10.5120/1938-2589,
author = { Sanjay Bhargava, G. N. Purohit },
title = { Construction of a Minimal Deterministic Finite Automaton from a Regular Expression },
journal = { International Journal of Computer Applications },
issue_date = { February 2011 },
volume = { 15 },
number = { 4 },
month = { February },
year = { 2011 },
issn = { 0975-8887 },
pages = { 16-27 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume15/number4/1938-2589/ },
doi = { 10.5120/1938-2589 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T20:03:39.370454+05:30
%A Sanjay Bhargava
%A G. N. Purohit
%T Construction of a Minimal Deterministic Finite Automaton from a Regular Expression
%J International Journal of Computer Applications
%@ 0975-8887
%V 15
%N 4
%P 16-27
%D 2011
%I Foundation of Computer Science (FCS), NY, USA
Abstract

This paper describes a method for constructing a minimal deterministic finite automaton (DFA) from a regular expression. It is based on a set of graph grammar rules for combining many graphs (DFA) to obtain another desired graph (DFA). The graph grammar rules are presented in the form of a parsing algorithm that converts a regular expression R into a minimal deterministic finite automaton M such that the language accepted by DFA M is same as the language described by regular expression R. The proposed algorithm removes the dependency over the necessity of lengthy chain of conversion, that is, regular expression --> NFA with ε-transitions --> NFA without ε-transitions --> DFA --> minimal DFA. Therefore the main advantage of our minimal DFA construction algorithm is its minimal intermediate memory requirements and hence, the reduced time complexity. The proposed algorithm converts a regular expression of size n in to its minimal equivalent DFA in O(n.log2n) time. In addition to the above, the time complexity is further shortened to O(n.logen) for n ≥ 75.

References
  1. Antimirov, V. . “Partial derivatives of regular expressions and finite automata constructions”. Theoretical Computer Science. vol. 155, no. 2, pp. 291-319.
  2. Ben-David, S., D. Fisman, and S. Ruah . “Embedding finite automata within regular expressions”. Theoretical Computer Science. vol. 404, no. 3, pp. 202-218.
  3. Berry, G. and R. Sethi . “From regular expressions to deterministic automata”. Theoretical Computer Science. vol. 48, no. 1, pp. 117-126.
  4. Berstel, J., D. Perrin, and C. Reutenauer . Codes and Automata. Encyclopedia of Mathematics and its Applications no. 129. Cambridge University Press. Cambridge.
  5. Bruggemann-Klein A. . “Regular expressions into finite automata”. Theoretical Computer Science. vol. 120, no. 2, pp. 197-213.
  6. Brzozowski, J. A. and R. Cohen . “On decompositions of regular events”. Journal of the ACM (J. ACM). vol. 16, no. 1, pp. 132-144.
  7. Carrasco, R. C., J. Daciuk, and M. L. Forcada . “Incremental construction of minimal tree automata”. Algorithmica. vol. 55, no. 1, pp. 95-110.
  8. Carrasco, R. C. and M. L. Forcada . “Incremental construction and maintenance of minimal finite-state automata”. Computational Linguistics. vol. 28, no. 2, pp. 207-216.
  9. Chang, C. H. and R. Paige . “From regular expressions to DFAs using compressed NFAs”. In Proceedings of the 3rd Annual Symposium on Combinatorial Pattern Matching. Lecture notes in Computer Science no. 644. Springer-Verlag, London. pp. 90-110.
  10. Cohen, D. I. A. . Introduction to Computer Theory. 2nd edn. John Wiley & Sons, Inc. New York.
  11. Daciuk, J., S. Mihov, B. W. Watson, and R. E. Watson . “Incremental construction of minimal acyclic finite-state automata”. Computational Linguistics. vol. 26, no. 1, pp. 3-16.
  12. Geffert, V. . “Translation of binary regular expressions into nondeterministic ε-free automata with o(nlogn) transitions”. Journal of Computer and System Sciences. vol. 66, no. 3, pp. 451-472.
  13. Ginzburg, A. . Algebraic Theory of Automata. Academic Press. New York.
  14. Glushkov, V. M. . “The abstract theory of automata”. Uspekhi Mathematicheskikh Nauk (UMN). vol. 16, no. 5(101), pp. 3-62.
  15. Greenlaw, R. and H. Hoover . Fundamentals of the Theory of Computation: Principles and Practice. Morgan Kaufmann Publishers, Inc. Elsevier, San Francisco, USA.
  16. Gurari, E. . An Introduction to the Theory of Computation. Computer Science Press. Ohio State University, Columbus, Ohio.
  17. Hagenah, C. and A. Muscholl . “Computing epsilon-free NFA from regular expressions in o(n.log²(n)) time”. In Proceedings of the 23rd International Symposium on Mathematical Foundations of Computer Science. Lecture Notes in Computer Science no. 1450. Springer-Verlag, London. pp. 277-285.
  18. Hein, J. L. . Theory of Computation. Jones & Bartlett Publishers, Inc. Sudbury, MA.
  19. Hopcroft, J. E. and J. Ullman . Introduction to Automata Theory, Languages and Computation. Addison-Wesley Longman Publishing Company, Inc. Boston, MA, USA.
  20. Hromkovic J., S. Seibert, and T. Wilke . ”Translating regular expressions into small ε-free nondeterministic finite automata”. Journal of Computer and System Sciences. vol. 62, no. 4, pp. 565-588.
  21. Ilie L. and S. Yu . “Follow automata”. Information and Computation. vol. 186, no. 1, pp. 140-162.
  22. Johnson, W. L., J. H. Porter, S. I. Ackley, and D. T. Ross . “Automatic generation of efficient lexical processors using finite state techniques”. Communications of the ACM. vol. 11, no. 12, pp. 805-813.
  23. Leiss, E. . “Constructing a finite automaton for a given regular expression”. ACM Special Interest Group on Algorithms and Computation Theory (ACM SIGACT News). vol. 12, no. 3, pp. 81-87.
  24. Lewis, H. R. and C. H. Papadimitriou . Elements of the Theory of Computation. 2nd edn. Pearson Education Asia. Delhi.
  25. Martin, J. . Introduction to Languages and the Theory of Computation. 3rd edn. Tata McGraw Hill. New Delhi.
  26. Mayr, Ernst W., G. Schmidt, and G. Tinhofer (eds.) . Graph-Theoretic Concepts in Computer Science. Lecture notes in Computer Science no. 903. Springer-Verlag, Berlin/Heidelberg, New York.
  27. Möhring, R. H. (ed.) . Graph-Theoretic Concepts in Computer Science, 16th International Workshop, WG '90, Berlin, Germany, June 20-22, 1990, Proceedings. Lecture Notes in Computer Science no. 484. Springer. London, UK.
  28. Rytter, W. . “A note on optimal parallel transformations of regular expressions to nondeterministic finite automata”. Information Processing Letters. vol. 31, no. 2, pp. 103-109.
  29. Singh, A. . Elements of Computation Theory. Springer-Verlag. London.
  30. Sipser, M. . Introduction to the Theory of Computation. 2nd edn. PWS Publishing.
  31. Stefano, C. R. . Formal Languages and Compilation. Springer-Verlag. London.
  32. Taylor, R. G. . Models of Computation and Formal Languages. Oxford University Press. New York.
  33. Thompson, K. . “Regular expression search algorithms”. Communications of the ACM. vol. 11, no. 6, pp. 419-422.
  34. Watson, B. . “Taxonomies and toolkits of regular language algorithms”. Ph.D. Thesis. Eindhoven University of Technology, CIP-DATA Koninklijke Bibliotheek, Den Haag.
  35. Wood, D. . Theory of Computation: A Primer. Addison-Wesley Longman Publishing Company, Inc. Boston, MA, USA.
  36. Yamamoto, H. . “New finite automata corresponding to semiextended regular expressions”. Systems and Computers in Japan. vol. 36, no. 10, pp. 54-61.
  37. Ziadi, D. and J. M. Champarnaud . “An optimal parallel algorithm to convert a regular expression into its Glushkov automaton”. Laboratoire d'Informatique de Rouen. vol. 215, no. 1-2, pp. 69-87.
Index Terms

Computer Science
Information Sciences

Keywords

Alphabet Automaton Construction Combined State Union Concatenation Kleene Closure Minimization Transition