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 |
![]() |
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
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.