Call for Paper - August 2022 Edition
IJCA solicits original research papers for the August 2022 Edition. Last date of manuscript submission is July 20, 2022. Read More

Construction of a Minimal Deterministic Finite Automaton from a Regular Expression

Print
PDF
International Journal of Computer Applications
© 2011 by IJCA Journal
Number 4 - Article 3
Year of Publication: 2011
Authors:
Sanjay Bhargava
G. N. Purohit
10.5120/1938-2589

Sanjay Bhargava and G N Purohit. Article: Construction of a Minimal Deterministic Finite Automaton from a Regular Expression. International Journal of Computer Applications 15(4):16–27, February 2011. Full text available. BibTeX

@article{key:article,
	author = {Sanjay Bhargava and G. N. Purohit},
	title = {Article: Construction of a Minimal Deterministic Finite Automaton from a Regular Expression},
	journal = {International Journal of Computer Applications},
	year = {2011},
	volume = {15},
	number = {4},
	pages = {16--27},
	month = {February},
	note = {Full text available}
}

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.

Reference

  • Antimirov, V. [1996]. “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 [2008]. “Embedding finite automata within regular expressions”. Theoretical Computer Science. vol. 404, no. 3, pp. 202-218.
  • Berry, G. and R. Sethi [1986]. “From regular expressions to deterministic automata”. Theoretical Computer Science. vol. 48, no. 1, pp. 117-126.
  • Berstel, J., D. Perrin, and C. Reutenauer [2009]. Codes and Automata. Encyclopedia of Mathematics and its Applications no. 129. Cambridge University Press. Cambridge.
  • Bruggemann-Klein A. [1993]. “Regular expressions into finite automata”. Theoretical Computer Science. vol. 120, no. 2, pp. 197-213.
  • Brzozowski, J. A. and R. Cohen [1969]. “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 [2009]. “Incremental construction of minimal tree automata”. Algorithmica. vol. 55, no. 1, pp. 95-110.
  • Carrasco, R. C. and M. L. Forcada [2001]. “Incremental construction and maintenance of minimal finite-state automata”. Computational Linguistics. vol. 28, no. 2, pp. 207-216.
  • Chang, C. H. and R. Paige [1992]. “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. [1991]. Introduction to Computer Theory. 2nd edn. John Wiley & Sons, Inc. New York.
  • Daciuk, J., S. Mihov, B. W. Watson, and R. E. Watson [2000]. “Incremental construction of minimal acyclic finite-state automata”. Computational Linguistics. vol. 26, no. 1, pp. 3-16.
  • Geffert, V. [2003]. “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. [1968]. Algebraic Theory of Automata. Academic Press. New York.
  • Glushkov, V. M. [1961]. “The abstract theory of automata”. Uspekhi Mathematicheskikh Nauk (UMN). vol. 16, no. 5(101), pp. 3-62.
  • Greenlaw, R. and H. Hoover [1998]. Fundamentals of the Theory of Computation: Principles and Practice. Morgan Kaufmann Publishers, Inc. Elsevier, San Francisco, USA.
  • Gurari, E. [1989]. An Introduction to the Theory of Computation. Computer Science Press. Ohio State University, Columbus, Ohio.
  • Hagenah, C. and A. Muscholl [1998]. “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. [1996]. Theory of Computation. Jones & Bartlett Publishers, Inc. Sudbury, MA.
  • Hopcroft, J. E. and J. Ullman [1979]. Introduction to Automata Theory, Languages and Computation. Addison-Wesley Longman Publishing Company, Inc. Boston, MA, USA.
  • Hromkovic J., S. Seibert, and T. Wilke [2001]. ”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 [2003]. “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 [1968]. “Automatic generation of efficient lexical processors using finite state techniques”. Communications of the ACM. vol. 11, no. 12, pp. 805-813.
  • Leiss, E. [1980]. “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 [2001]. Elements of the Theory of Computation. 2nd edn. Pearson Education Asia. Delhi.
  • Martin, J. [2004]. Introduction to Languages and the Theory of Computation. 3rd edn. Tata McGraw Hill. New Delhi.
  • Mayr, Ernst W., G. Schmidt, and G. Tinhofer (eds.) [1995]. Graph-Theoretic Concepts in Computer Science. Lecture notes in Computer Science no. 903. Springer-Verlag, Berlin/Heidelberg, New York.
  • Möhring, R. H. (ed.) [1991]. 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. [1989]. “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. [2009]. Elements of Computation Theory. Springer-Verlag. London.
  • Sipser, M. [2006]. Introduction to the Theory of Computation. 2nd edn. PWS Publishing.
  • Stefano, C. R. [2009]. Formal Languages and Compilation. Springer-Verlag. London.
  • Taylor, R. G. [1998]. Models of Computation and Formal Languages. Oxford University Press. New York.
  • Thompson, K. [1968]. “Regular expression search algorithms”. Communications of the ACM. vol. 11, no. 6, pp. 419-422.
  • Watson, B. [1995]. “Taxonomies and toolkits of regular language algorithms”. Ph.D. Thesis. Eindhoven University of Technology, CIP-DATA Koninklijke Bibliotheek, Den Haag.
  • Wood, D. [1987]. Theory of Computation: A Primer. Addison-Wesley Longman Publishing Company, Inc. Boston, MA, USA.
  • Yamamoto, H. [2005]. “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 [1999]. “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.