A Novel Algorithm for Reduction of Non-Deterministic Finite Automata

In automata theory a minimization is the task of transforming a given finite state machine into an equivalent automation that has a minimum number of states. Here, the reduction of Deterministic Finite Automata(DFA) is very simple whereas Nondeterministic Finite Automata(NFA) is complex because which has maximium number of possible paths to reach new states. So a minimal NFA is a primal problem in automata theory.

We consider the problem of approximating a minimal NFA or a minimal regular expression. There are several approaches to NFA minimization either without approximation guarantees or running in at least exponential time. Here this paper introducing the new NFA reduction algorithm for the minimization of NFA.

This algorithm will reduce number of state transitions of Nondeterministic Finite Automata. NFA reduction algorithm also resolves the complexity of Kameda- Weiner algorithm. This paper shown empirically that this algorithm is effective in largely reducing the memory requirement of NFA minimization algorithm.

Reducing the size of NFA by using NFA Reduction Algorithm has been shown to reduce importantly the search time.

by G. Mutyalamma | K. Komali | G. Pushpa "A Novel Algorithm for Reduction of Non-Deterministic Finite Automata"

Published in International Journal of Trend in Scientific Research and Development (ijtsrd), ISSN: 2456-6470, Volume-2 | Issue-1 , December 2017,

URL: http://www.ijtsrd.com/papers/ijtsrd8233.pdf

Direct Link - http://www.ijtsrd.com/computer-science/other/8233/a-novel-algorithm-for-reduction-of--non-deterministic-finite-automata/g-mutyalamma

International Journal