Applications of deterministic and non-deterministic finite automata

Document Type : Research Paper

Author

Department of Mathematics, Faculty of Basic Sciences, Shahid Madani University of Azerbaijan

Abstract

Topics related to formal languages and suitable models for them are fundamental concepts in the field of computer science. Among the simplest computational models are finite automata. The reason for the simplicity of these types of machines is that they do not have auxiliary memory; nevertheless, many problems can be solved using finite automata. In this article, the concept of deterministic and non-deterministic finite automata is introduced. Then, finite automata are used in text search for a specific pattern. Additionally, the process of online shopping is modeled using finite automata.

Keywords


[1] M. Crochemore and T. Lecroq, Pattern matching and textcompression algorithms, The computer science and engineering Handbook, A. B Tucker, Jr. ed., CRC Press, Boca Raton, 2003.
[2] K. Culik II and J. Kari, Image compression using weighted finite automata, Mathematical foundations of computer science, Lecture Notes in Comput. Sci., 711, Springer, Berlin, (1993) 392–402.
[3] D. Ding-Zhu and K. Ker-I., Problem Solving in Automata, Languages and Complexity, 1st edition, New York, Wiley-
Interscience, 2001.
[4] J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979.
[5] D. A. Huffman, The synthesis of sequential switching circuits, J. Franklin Inst., 257 (1954) 275–303.
[6] P. Linz, Introduction to Formal Languages and Automata, 5th edition, Canada, Jones Bartlett Learning, 2011.
[7] J. C. Martin, Introduction to Languages and The Theory of Computation, 4th edition, New York, McGraw-Hill Education, 2010.
[8] G. Navarro and R. Baeza- Yates, Improving an Algorithm for Approximate Pattern Matching, Algorithmica, 30 (2001) 473–502.
[9] M. O. Rabin and D. Scott, Finite automata and their decision problems, IBM J. Res. Develop, 3 (1959) 114–125.
10] M. Sipser, Introduction to the Theory of Computation, 3rd edition, United States, Cengage Learning, 2012.