Finite automata and formal language recognition
DOI:
https://doi.org/10.70577/asce.v5i2.775Keywords:
Automation, Determinism, Programming language, Lexicography, Character recognitionAbstract
Finite automata are considered fundamental pillars for structured information processing, as they constitute the primary tool for recognizing formal languages, specifically those classified as regular. The objective of this research is to analyze the theoretical foundations of finite automata and explain their function in the recognition of formal languages. A literature review was conducted with a critical, descriptive, and analytical approach; the PRISMA method was applied; previously published scientific articles were compiled from academic databases; and filters were applied as inclusion and exclusion criteria, taking into account the research questions and objectives. A comparison of finite automata and their relationship to formal languages was made. It was found that every non-deterministic finite automaton has an equivalent deterministic finite automaton that recognizes the same language, guaranteeing that non-determinism does not increase expressive power. The robustness of formal languages is based on their closure properties, which allow finite automata to move beyond the theoretical realm and be integrated into critical engineering applications. It was concluded that finite automata are consolidated as the most elementary level of the Chomsky hierarchy and regular grammars. The algebraic closure properties allow these models to be integrated into critical applications such as formal verification. In future research, it is recommended to prioritize the use of minimized deterministic finite automata in the development of lexical analyzers for compilers and pattern recognition engines.
Downloads
References
Allamanis, M., Barr, E. T., Devanbu, P., & Sutton, C. (2019). A Survey of Machine Learning for Big Code and Naturalness. ACM Computing Surveys, 51(4), 1-37. https://doi.org/10.1145/3212695
Broy, M., Brucker, A. D., Fantechi, A., Gleirscher, M., Havelund, K., Kuppe, M. A., Mendes, A., Platzer, A., Ringert, J. O., & Sullivan, A. (2025). Does Every Computer Scientist Need to Know Formal Methods? Formal Aspects of Computing, 37(1), 1-17. https://doi.org/10.1145/3670795
Cummins, C., Seeker, V., Grubisic, D., Elhoushi, M., Liang, Y., Roziere, B., Gehring, J., Gloeckle, F., Hazelwood, K., Synnaeve, G., & Leather, H. (2023). Large Language Models for Compiler Optimization (Versión 1). arXiv. https://doi.org/10.48550/ARXIV.2309.07062
Dhayalkar, S. R. (2025). Neural Networks as Universal Finite-State Machines: A Constructive Deterministic Finite Automaton Theory (Versión 2). arXiv. https://doi.org/10.48550/ARXIV.2505.11694
Dora, J. R., Hluchý, L., & Staňo, M. (2025). In-Memory Shellcode Runner Detection in Internet of Things (IoT) Networks: A Lightweight Behavioral and Semantic Analysis Framework. Sensors, 25(17), 5425. https://doi.org/10.3390/s25175425
Figueiras, P., Ioannou, G., Lambri, C., Reji, S., Mossali, E., Neviani, M. I., Koussouris, S., Bountouni, N., In Cugurra, M. D. B., Hellbach, R., Bibikas, D., O’Brien, P., Agostinho, C., & Jardim-Gonçalves, R. (2026). Roadmaps and Agendas for Research and Innovation in Artificial Intelligence, Data, and Robotics. En E. Curry, P. Piatkiewicz, F. Heintz, H. Vornhagen, A. N. Belbachir, E. Girardi, M. Schoenauer, & J. Röning (Eds.), Artificial Intelligence, Data and Robotics (pp. 547-579). Springer Nature Switzerland. https://doi.org/10.1007/978-3-032-10561-5_19
Gambhire, S., Panhalkar, A. R., Patil, D. H., Kedar, S., Kumar, M., & Panchal, B. Y. (2026). Leveraging formal languages and automata theory in natural language processing (NLP). Journal of Discrete Mathematical Sciences & Cryptography, 29(2-B), 995-1004. https://doi.org/10.47974/JDMSC-2552
Hou, Z. (2021). Automata Theory and Formal Languages. En Z. Hou, Fundamentals of Logic and Computation (pp. 119-162). Springer International Publishing. https://doi.org/10.1007/978-3-030-87882-5_4
Kamble, U., Nalawade, S., Mahadik, T., Salunke, Y., Dedgaonkar, S., & Shelke, P. (2024). Survey of Application of Automata Theory in Natural Language Processing. 2024 ASU International Conference in Emerging Technologies for Sustainability and Intelligent Systems (ICETSIS), 1-4. https://doi.org/10.1109/ICETSIS61505.2024.10459556
Karakonstantis, I., & Xylomenos, G. (2026). A Review of Two-Dimensional Cellular Automata Models for Wildfire Simulation: Methods, Capabilities, and Limitations. Fire, 9(3), 108. https://doi.org/10.3390/fire9030108
Kumar, A., Awasthy, N., Jose, A. S., Ramesh, G., Gupta, M., Srinija, K., & Najm, R. (2025). The Intersection of Algorithms, Automata Theory, and Formal Languages in Computational Theory. 2025 International Conference on Intelligent Control, Computing and Communications (IC3), 691-697. https://doi.org/10.1109/IC363308.2025.10956289
Morazán, M. T., & Minić, T. (2024). Finite-State Automaton To/From Regular Expression Visualization. https://doi.org/10.48550/ARXIV.2407.08088
Nagy, B. (2022). From Finite Automata to Fractal Automata – The Power of Recursion. En J. Durand-Lose & G. Vaszil (Eds.), Machines, Computations, and Universality (Vol. 13419, pp. 109-125). Springer International Publishing. https://doi.org/10.1007/978-3-031-13502-6_8
Negrini, L., Arceri, V., Cortesi, A., & Ferrara, P. (2024). TARSIS: An effective automata‐based abstract domain for string analysis. Journal of Software: Evolution and Process, 36(8), e2647. https://doi.org/10.1002/smr.2647
Nicol, J., & Frohme, M. (2025). Deconstructing Subset Construction—Reducing While Determinizing (Versión 2). arXiv. https://doi.org/10.48550/ARXIV.2505.10319
Postiglione, A. (2024). Finite State Automata on Multi-Word Units for Efficient Text-Mining. Mathematics, 12(4), 506. https://doi.org/10.3390/math12040506
Seshia, S. A., Sharygina, N., & Tripakis, S. (2018). Modeling for Verification. En E. M. Clarke, T. A. Henzinger, H. Veith, & R. Bloem (Eds.), Handbook of Model Checking (pp. 75-105). Springer International Publishing. https://doi.org/10.1007/978-3-319-10575-8_3
Urbat, H., & Schröder, L. (2020). Automata Learning: An Algebraic Approach. Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, 900-914. https://doi.org/10.1145/3373718.3394775
Yadav, A., Patel, A., & Shah, M. (2021). A comprehensive review on resolving ambiguities in natural language processing. AI Open, 2, 85-92. https://doi.org/10.1016/j.aiopen.2021.05.001
Yokomori, T., & Okubo, F. (2021). Theory of reaction automata: A survey. Journal of Membrane Computing, 3(1), 63-85. https://doi.org/10.1007/s41965-021-00070-6
Yue, J., Yan, Y., & Chen, Z. (2019). Language acceptability of finite automata based on theory of semi‐tensor product of matrices. Asian Journal of Control, 21(6), 2634-2643. https://doi.org/10.1002/asjc.2190
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2026 Angel Yael Sarabia Martínez
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Eres libre de:
- Compartir : copiar y redistribuir el material en cualquier medio o formato
- Adaptar : remezclar, transformar y desarrollar el material
- El licenciante no puede revocar estas libertades siempre y cuando usted cumpla con los términos de la licencia.
En los siguientes términos:
- Atribución : Debe otorgar el crédito correspondiente , proporcionar un enlace a la licencia e indicar si se realizaron cambios . Puede hacerlo de cualquier manera razonable, pero no de ninguna manera que sugiera que el licenciante lo respalda a usted o a su uso.
- No comercial : no puede utilizar el material con fines comerciales .
- CompartirIgual — Si remezcla, transforma o construye sobre el material, debe distribuir sus contribuciones bajo la misma licencia que el original.
- Sin restricciones adicionales : no puede aplicar términos legales ni medidas tecnológicas que restrinjan legalmente a otros hacer algo que la licencia permite.
