A Novel Approach to Minimize DFA State Machines Using Linked List

Yogesh Pant¹

Section:Research Paper, Product Type: Isroset-Journal
Vol.6 , Issue.4 , pp.41-45, Aug-2018

CrossRef-DOI:   https://doi.org/10.26438/ijsrcse/v6i4.4145

Online published on Aug 31, 2018

Copyright © Yogesh Pant . This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
 

View this paper at   Google Scholar | DPI Digital Library

XML View     PDF Download

How to Cite this Paper

1316 Views    514 Downloads    126 Downloads

Abstract :
DFA minimization is a significant problem in algorithm design. Minimization of DFA works on the concept of DFA equivalence: Two DFA’s are equivalent if and only if both accept the identical strings of same set. Plethora of computational problems can be solved simply by using the encoding method. Combinatorial objects which are to be used as strings over a finite alphabet can be encoded. Standard algorithms from computational linear algebra are subjected to be used efficiently to solve the computational problems if a DFA recognize the set of encoded strings. This proposed method provides better results whereas other methods may face serious problem of time and space complexities.

Key-Words / Index Term :
DFA; NFA; Regular expressions; Compiler Design; Linked List

References :
[1] Ernest ketcha am, derrick g. kourie, and brucngasse w. watson,“On Implementation and Performance of Table-Driven DFA-Based String Processors”. Int. J. Found. Comput. Sci. 19, 53 (2008).
[2] Bruce William Watson, “Constructing Minimal Acyclic Deterministic Finite Automata”. FASTAR Research Group.
[3] Domenico Ficara, Stefano Giordano, Gregorio Procissi, Fabio Vitucci, Gianni Antichi, and Andrea Di Pietro.. “An improved DFA for fast regular expression matching”, SIGCOMM Comput. Commun. Rev. 38, September 2008.
[4] Todd J. Green, Ashish Gupta, Gerome Miklau, Makoto Onizuka, and Dan Suciu. “Processing XML streams with deterministic automata and stream indexes”, ACM Trans. Database Syst. 29, 4 (December 2004)
[5] Isaac Keslassy, David Hay, Yossi Kanizo, Isaac Keslassy, David Hay, Yossi Kanizo. “Optimal Fast Hashing”, Technical Report Tr08-05, Comnet, Technion, Israel.
[6] Aho, Alfred V.; Hopcroft, John E.; Ullman, Jeffrey D. (1974), 4.13 Partitioning, “The Design and Analysis of Computer Algorithms”, Addison-Wesley, pp. 157–162.
[7] Aakanksha Pandey, Dr. Nilay Khare and Akhtar Rasool“Efficient Design and Implementation of DFA Based Pattern Matching on Hardware”, IJCSI March 2012.
[8] B. L. Hutchings and R. Franklin and D. Carver “Scalable Hardware Implementation on Finite Automata” Department of Electrical and Computer Engineering
[9] S. Kumar, S. Dharmapurikar, F. Yu, P. Crowley, and J. Turner . “ Algorithms to accelerate multiple regular expressions matching for deep packet inspection”, In Proc. of SIGCOMM `06, pages 339-350. ACM.
[10] R. Smith, C. Estan, and S. Jha. Xfa, “Faster signature matching with extended automata”, In IEEE Symposium on Security and Privacy, May 2008.
[11] Vlad Slavici, Daniel Kunkle, Gene Cooperman and Stephen Linton, “Finding the Minimal DFA of Very Large Finite State Automata with an Application to Token Passing Networks” Northeastern University, 29 March 2011.