Google scholar arxiv informatics ads IJAIS publications are indexed with Google Scholar, NASA ADS, Informatics et. al.

Call for Paper


April Edition 2021

International Journal of Applied Information Systems solicits high quality original research papers for the April 2021 Edition of the journal. The last date of research paper submission is March 15, 2021.

LR Rotation Rule for Creating Minimal NFA

Himanshu Pandey, V. K Singh, Neeraj Kumar Verma Published in Algorithms

International Journal of Applied Information Systems
Year of Publication: 2015
© 2015 by IJAIS Journal
Download full text
  1. Himanshu Pandey, V K Singh and Neeraj Kumar Verma. Article: LR Rotation Rule for Creating Minimal NFA. International Journal of Applied Information Systems 8(6):1-4, April 2015. BibTeX

    	author = "Himanshu Pandey and V. K Singh and Neeraj Kumar Verma",
    	title = "Article: LR Rotation Rule for Creating Minimal NFA",
    	journal = "International Journal of Applied Information Systems",
    	year = 2015,
    	volume = 8,
    	number = 6,
    	pages = "1-4",
    	month = "April",
    	note = "Published by Foundation of Computer Science, New York, USA"


The problem of creating a minimal NFA is a primal (fundamental) problem. Reducing the size of NFA by using LR rotation rule has been shown to reduce importantly the search time. In [1] Ilie and Yu describe a construction of a right invariant equivalence relation on the states of a non-deterministic finite state automaton. We give a more efficient LR Rotation rule for constructing the minimal NFA. In this paper we represent new LR Rotation rule for the state minimization of NFA. The description of the proposed methods is given and we also shown the results of the numerical experiments. We conceive the problem of reducing the number of state and transition of Non Deterministic Finite Automata. Numerical experiments show that NFA reduction algorithm produces a minimal automation in all most cases. NFA reduction algorithm also reduces the complexity of Kameda-Weiner algorithm. We have shown empirically that these algorithms are effective in largely reducing the memory requirement of NFA minimization algorithm and algorithm minimization of the number of rules for NFA grows each year.


  1. L. llie, Roberto Solis-Oba, Sheng yu: 2005,"Reducing the Size of NFAs by Using Equivalences and Preorders", Lecture Notes in Computer Science, Volume 3537, 2005, pp 310-321 in Springer.
  2. M. Albert and Steve Linton: July 2014, "A Practical Algorithm for Reducing Non-Deterministic Finite State Automata", Elsevier Science.
  3. A V. Tsyganov: September 2012, "Local Search Heuristics for NFA State Minimization Problem", Int. J. Communications, Network and System Sciences, 2012, 5, 638-643.
  4. H. Gruber and M. Holzer: "Computational Complexity of NFA Minimization for Finite and Unary Languages",Institut f¨ur Informatik, Ludwig-Maximilians-Universit¨at M¨unchen, Oettingenstraße 67, D-80538 M¨unchen, Germany.
  5. H. Bj¨orklunda, Wim Martens: April 2011, "The Tractability Frontier for NFA Minimization", International Colloquium on Automata, Languages and Programming 2008.
  6. Y. Zhou Yuliu Chen, "The QFD-based Decision-making Approach for Strategic BPR" Beijing 100084, P. R. China.
  7. G. Xing, August 20-22, 2007 "Minimized Thompson NFA", Western Kentucky University, Bowling Green, KY 42101.
  8. V. Garg, Anu: June 2013, "DFA Minimizing State Machines Using Hash- Tables", International Journal of Engineering Trends and Technology (IJETT) - Volume4 Issue6- June 2013.
  9. V. Ko?sa?r, Martin ?Z ´adn´?k, Jan Ko?renek, 2007 "NFA Reduction for Regular Expressions Matching Using FPGA", MSM 0021630528, the IT4Innovations Centre of Excellence CZ. 1. 05/1. 1. 00/02. 0070 and the grant BUT FIT-S-11-1.
  10. M. Vázquez de Parga, P. García, Damián López, 2013 "A polynomial double reversal minimization algorithm for deterministic finite automata", Theoretical Computer Science 487 (2013) 17–22.
  11. J. Vuillemin, N. Gama: Dec 2009, "Efficient Equivalence and Minimization for Non Deterministic Xor Automata", [Research Report] 2010, pp. 25. .
  12. W. Wieczorek: 2012, "Induction of Non-Deterministic Finite Automata on Supercomputers", JMLR: Workshop and Conference Proceedings 21:237{242, 2012. The 11th ICGI.
  13. M. Mohri, F. Pereira and M. Riley, "AT&T General- Purpose Finite-State Machine Software Tools," 1997. http://www. research. att. com/sw/tools/fsm
  14. S. Lombardy, R. Poss, Y. Régis-Gianas and J. Sa-karovitch, "Introducing VAUCANSON," In: O. H. Ibarra and Z. Dang, Eds. , Implementation and Application of Automata, CIAA 2003, Santa Barbara, 16-18 July 2003, pp. 96-107.
  15. S. H. Rodger, "JFLAP: An Interactive Formal Languages and Automata Package," Jones and Bartlett Publishers, Inc. , USA, 2006.
  16. T. Kameda and P. Weiner, "On the State Minimization of Nondeterministic Finite Automata," IEEE Transactions on Computers, Vol. C-19, No. 7, 1970, pp. 617-627. doi:10. 1109/T-C. 1970. 222994
  17. J. Hromkovic, "Algorithmics for Hard Problems—Intro- duction to Combinatorial Optimization, Randomization, Approximation, and Heuristics," Springer, Berlin, 2001.
  18. F. Glover and G. A. Kohenberger, "Handbook of Meta-heuristics," Kluwer Academic Publishers, Boston, 2003.
  19. V. Kell, A. Maier, A. Potthoff, W. Thomas and U. Wer-muth, "AMORE: A System for Computing Automata, Monoids and Regular Expressions," Proceedings of the 6th Annual Symposium on Theoretical Aspects of Com-puter Science on STACS 89, Springer-Verlag, New York,


NFA, Algorithm