CFP last date
20 January 2025
Call for Paper
February Edition
IJCA solicits high quality original research papers for the upcoming February edition of the journal. The last date of research paper submission is 20 January 2025

Submit your paper
Know more
The week's pick
Responsive image
SFLA-Based Line Balancing and Task Optimization in Master-Slave Controlled Hanger Transportation Systems for Garment Production

Duc Hoang Nguyen
Random Articles
Reseach Article

Construction of a Minimal Deterministic Finite Automaton from a Regular Expression

by Sanjay Bhargava, G. N. Purohit
journal cover thumbnail

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

Powered by PhDFocusTM