Home > Computer Science > Other > Volume-2 > Issue-1 > A Novel Algorithm for Reduction of Non-Deterministic Finite Automata

A Novel Algorithm for Reduction of Non-Deterministic Finite Automata

Call for Papers

Volume-5 | Issue-6

Last date : 26-Oct-2021

Best International Journal
Open Access | Peer Reviewed | Best International Journal | Indexing & IF | 24*7 Support | Dedicated Qualified Team | Rapid Publication Process | International Editor, Reviewer Board | Attractive User Interface with Easy Navigation

Journal Type : Open Access

Processing Charges : 700/- INR Only OR 25 USD (for foreign users)

First Update : Within 7 Days after submittion

Submit Paper Online

For Author

Research Area

A Novel Algorithm for Reduction of Non-Deterministic Finite Automata

G. Mutyalamma | K. Komali | G. Pushpa


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, pp.1341-1346, URL: https://www.ijtsrd.com/papers/ijtsrd8233.pdf

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.

Non Deterministic Finite Automata (NFA), Simplest Automation Matrix, Simplified Functional Matrix (SFM), Transition table, Transition function

Volume-2 | Issue-1, December 2017
IJTSRD | www.ijtsrd.com | E-ISSN 2456-6470
Copyright © 2019 by author(s) and International Journal of Trend in Scientific Research and Development Journal. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (CC BY 4.0) (http://creativecommons.org/licenses/by/4.0)

International Journal of Trend in Scientific Research and Development - IJTSRD having online ISSN 2456-6470. IJTSRD is a leading Open Access, Peer-Reviewed International Journal which provides rapid publication of your research articles and aims to promote the theory and practice along with knowledge sharing between researchers, developers, engineers, students, and practitioners working in and around the world in many areas like Sciences, Technology, Innovation, Engineering, Agriculture, Management and many more and it is recommended by all Universities, review articles and short communications in all subjects. IJTSRD running an International Journal who are proving quality publication of peer reviewed and refereed international journals from diverse fields that emphasizes new research, development and their applications. IJTSRD provides an online access to exchange your research work, technical notes & surveying results among professionals throughout the world in e-journals. IJTSRD is a fastest growing and dynamic professional organization. The aim of this organization is to provide access not only to world class research resources, but through its professionals aim to bring in a significant transformation in the real of open access journals and online publishing.

Thomson Reuters
Google Scholer