Non-Deterministic Finite Automata to Deterministic Finite Automata Conversion by Subset Construction Method using Python

Authors

  • Vayadande K Department of Artificial Intelligence and Data Science, Vishwakarma Institute of Technology, Pune, India
  • Patel K Department of Artificial Intelligence and Data Science, Vishwakarma Institute of Technology, Pune, India
  • Punde N Department of Artificial Intelligence and Data Science, Vishwakarma Institute of Technology, Pune, India
  • Patil S Department of Artificial Intelligence and Data Science, Vishwakarma Institute of Technology, Pune, India
  • Nikam S Department of Artificial Intelligence and Data Science, Vishwakarma Institute of Technology, Pune, India
  • Pathrabe S Department of Artificial Intelligence and Data Science, Vishwakarma Institute of Technology, Pune, India

DOI:

https://doi.org/10.26438/ijcse/v10i1.15

Keywords:

DFA, Finite Automata, NFA, NFA to DFA,, Streamlit Web Application.

Abstract

The theory of finite automata, formal languages and complexity are the modern branches in the field of computer theory and their mathematical models play a very important role in the practical world. This makes it really important, in theory as well as practice to translate a Non-deterministic Finite Automata (NFA) into a Deterministic Finite Automata (DFA). Many different approaches are developed for doing so. In this paper, an optimized algorithm for transition from NFA to DFA is given. This method is implemented using the programming language called python3. Along with this we have also used the pandas library of python for constructing the transition tables for NFA as well as DFA. A website for the same is also created to make it more user friendly by using the streamlit library of python.

References

[1] Jing Maohua, G.-R. Li, W.-B. Shi, S.-X. Cai, “Improved conversion algorithm from NFA to DFA”, Dongbei Daxue Xuebao/Journal of Northeastern University, Vol.33(4), April 2012.

[2] C. H. Chanh, R. Paige, “From regular expression to DFA using compressed NFA”, Theoretical Computer Science, Vol.178, Issue.1-2, pp.1-36, May 1997.

[3] N.Murugesan, O. V. Shanmuga Sundaram, “A General Approach to DFA Construction”, International Journal of Research in Computer Science, Vol.2, Issue.4, pp.12-17, 2015.

[4] P. Linz, “An Introduction to formal languages and Automata”, D. C. Health and Company, 1996.

[5] K. Salomaa, S. Yu, “NFA to DFA conversion for finite languages”, Lecture Notes in Computer Science, pp.149-158, 2006.

[6] M. Sipser, “An Introduction to the Theory of Computation”, Second Edition, Thomson Course Technology, 2006.

[7] M. Davoudi-Monfared, R. shafiezadeh garousi, E. S. Haghi, S. Zeinali and S.Mohebali, “Converting different automata with programming C++”, International Journal of Advanced Computer Research, Vol.5, Issue.21, December 2015.

[8] Raza, Mir Adil, Kuldeep Baban Vayadande, and H. D. Preetham. "DJANGO MANAGEMENT OF MEDICAL STORE.", International Research Journal of Modernization in Engineering Technology and Science, Vol.2, Issue.11, November 2020.

[9] K.B. Vayadande, Nikhil D. Karande,” Automatic Detection and Correction of Software Faults: A Review Paper”, International Journal for Research in Applied Science & Engineering Technology (IJRASET) ISSN: 2321-9653, Vol.8, Issue.4, April 2020.

[10] Kuldeep Vayadande, Ritesh Pokarne, Mahalaxmi Phaldesai, Tanushri Bhuruk, Tanmai Patil, Prachi Kumar, “SIMULATION OF CONWAY’S GAME OF LIFE USING CELLULAR AUTOMATA” International Research Journal of Engineering and Technology, Vol.9, Issue.1, Jan 2022, e-ISSN: 2395-0056, p-ISSN: 2395-0072.

[11] Kuldeep Vayadande, Harshwardhan More, Omkar More, Shubham Mulay, Atharva Pathak, Vishwam Talnikar, “ Pac Man: Game Development using PDA and OOP”, International Research Journal of Engineering and Technology (IRJET), Volume: 09 Issue: 01 | Jan 2022, e-ISSN: 2395-0056, p-ISSN: 2395-0072.

Downloads

Published

2022-01-31
CITATION
DOI: 10.26438/ijcse/v10i1.15
Published: 2022-01-31

How to Cite

[1]
K. Vayadande, K. Patel, N. Punde, S. Patil, S. Nikam, and S. Pathrabe, “Non-Deterministic Finite Automata to Deterministic Finite Automata Conversion by Subset Construction Method using Python”, Int. J. Comp. Sci. Eng., vol. 10, no. 1, pp. 1–5, Jan. 2022.

Issue

Vol. 10 No. 1 (2022): IJCSE January Edition

Section

Research Article

License

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

Authors contributing to this journal agree to publish their articles under the Creative Commons Attribution 4.0 International License, allowing third parties to share their work (copy, distribute, transmit) and to adapt it, under the condition that the authors are given credit and that in the event of reuse or distribution, the terms of this license are made clear.