|International Journal of Applied Information Systems|
|Foundation of Computer Science (FCS), NY, USA|
|Volume 8 - Number 6|
|Year of Publication: 2015|
|Authors: Himanshu Pandey, V. K Singh, Neeraj Kumar Verma|
Himanshu Pandey, V. K Singh, Neeraj Kumar Verma . LR Rotation Rule for Creating Minimal NFA. International Journal of Applied Information Systems. 8, 6 ( April 2015), 1-4. DOI=10.5120/ijais15-451324
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  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.