Autómatas finitos y reconocimiento de lenguajes formales
DOI:
https://doi.org/10.70577/asce.v5i2.775Palabras clave:
Automatización, Determinismo, Lenguaje de programación, Lexicografía, Reconocimiento de caracteresResumen
Los autómatas finitos son considerados pilares fundamentales para el procesamiento de información estructurada, pues, constituyen la herramienta primordial para el reconocimiento de lenguajes formales, específicamente de aquellos clasificados como regulares. El objetivo de la investigación es analizar los fundamentos teóricos de los autómatas finitos y explicar su función en el reconocimiento de lenguajes formales. Se realizó una revisión bibliográfica con enfoque crítico, descriptivo y analítico; se aplicó el método PRISMA; se recopilaron Artículos Científicos (AC) previamente publicados en bases de datos académicas; se aplicaron filtros como criterios de inclusión y exclusión tomando en cuenta las preguntas y objetivos de investigación. Se comparó a los autómatas finitos y su relación con los lenguajes formales, se conoció que todo autómata finito no determinista tiene un autómata finito determinista equivalente que reconoce el mismo lenguaje, lo que garantiza que el no determinismo, no incrementa el poder expresivo; la robustez de los lenguajes formales se sustenta en sus propiedades de cerradura, pues, permite que los autómatas finitos superen el ámbito teórico para integrarse en aplicaciones críticas de ingeniería. Se concluyó que, los autómatas finitos se consolidan como el nivel más elemental de la jerarquía de Chomsky y las gramáticas regulares; las propiedades de cerradura algebraica permiten integrar estos modelos en aplicaciones críticas como la verificación formal; en investigaciones posteriores, se recomienda priorizar el uso de autómatas finitos deterministas minimizados en el desarrollo de analizadores léxicos para compiladores y motores de búsqueda de patrones.
Descargas
Citas
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
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
Derechos de autor 2026 Angel Yael Sarabia Martínez
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
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.
