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

• Antimirov, V. . “Partial derivatives of regular expressions and finite automata constructions”. Theoretical Computer Science. vol. 155, no. 2, pp. 291-319.
• Ben-David, S., D. Fisman, and S. Ruah . “Embedding finite automata within regular expressions”. Theoretical Computer Science. vol. 404, no. 3, pp. 202-218.
• Berry, G. and R. Sethi . “From regular expressions to deterministic automata”. Theoretical Computer Science. vol. 48, no. 1, pp. 117-126.
• Berstel, J., D. Perrin, and C. Reutenauer . Codes and Automata. Encyclopedia of Mathematics and its Applications no. 129. Cambridge University Press. Cambridge.
• Bruggemann-Klein A. . “Regular expressions into finite automata”. Theoretical Computer Science. vol. 120, no. 2, pp. 197-213.
• Brzozowski, J. A. and R. Cohen . “On decompositions of regular events”. Journal of the ACM (J. ACM). vol. 16, no. 1, pp. 132-144.
• Carrasco, R. C., J. Daciuk, and M. L. Forcada . “Incremental construction of minimal tree automata”. Algorithmica. vol. 55, no. 1, pp. 95-110.
• 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.
• 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.
• Cohen, D. I. A. . Introduction to Computer Theory. 2nd edn. John Wiley & Sons, Inc. New York.
• 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.
• 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.
• Ginzburg, A. . Algebraic Theory of Automata. Academic Press. New York.
• Glushkov, V. M. . “The abstract theory of automata”. Uspekhi Mathematicheskikh Nauk (UMN). vol. 16, no. 5(101), pp. 3-62.
• Greenlaw, R. and H. Hoover . Fundamentals of the Theory of Computation: Principles and Practice. Morgan Kaufmann Publishers, Inc. Elsevier, San Francisco, USA.
• Gurari, E. . An Introduction to the Theory of Computation. Computer Science Press. Ohio State University, Columbus, Ohio.
• 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.
• Hein, J. L. . Theory of Computation. Jones & Bartlett Publishers, Inc. Sudbury, MA.
• Hopcroft, J. E. and J. Ullman . Introduction to Automata Theory, Languages and Computation. Addison-Wesley Longman Publishing Company, Inc. Boston, MA, USA.
• 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.
• Ilie L. and S. Yu . “Follow automata”. Information and Computation. vol. 186, no. 1, pp. 140-162.
• 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.
• 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.
• Lewis, H. R. and C. H. Papadimitriou . Elements of the Theory of Computation. 2nd edn. Pearson Education Asia. Delhi.
• Martin, J. . Introduction to Languages and the Theory of Computation. 3rd edn. Tata McGraw Hill. New Delhi.
• 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.
• 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.
• 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.
• Singh, A. . Elements of Computation Theory. Springer-Verlag. London.
• Sipser, M. . Introduction to the Theory of Computation. 2nd edn. PWS Publishing.
• Stefano, C. R. . Formal Languages and Compilation. Springer-Verlag. London.
• Taylor, R. G. . Models of Computation and Formal Languages. Oxford University Press. New York.
• Thompson, K. . “Regular expression search algorithms”. Communications of the ACM. vol. 11, no. 6, pp. 419-422.
• Watson, B. . “Taxonomies and toolkits of regular language algorithms”. Ph.D. Thesis. Eindhoven University of Technology, CIP-DATA Koninklijke Bibliotheek, Den Haag.
• Wood, D. . Theory of Computation: A Primer. Addison-Wesley Longman Publishing Company, Inc. Boston, MA, USA.
• Yamamoto, H. . “New finite automata corresponding to semiextended regular expressions”. Systems and Computers in Japan. vol. 36, no. 10, pp. 54-61.
• 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.