2026-06-29T07:48:16Zhttps://docta.ucm.es/rest/oai/requestoai:docta.ucm.es:20.500.14352/104342023-09-06T21:43:49Zcom_20.500.14352_1col_20.500.14352_8
Comprobación de equivalencia entre especificaciones basadas en expresiones regulares
Checking equivalence of specifications based on regular expressions
Benito Montoro, Raúl
Chen, Xukai
Sierra Rodríguez, José Luis
004(043.3)
Algoritmo Hopcroft-Karp
Equivalencia
Expresiones regulares
Algoritmo deThompson
Algoritmo derivadas
Algoritmo derivadas parciales
Algoritmo Berry-Sethi
Algoritmo seguidores
Autómata finito
Determinación de autómatas.
Hopcroft-Karp algorithm
Equivalence
Thompson algorithm
Derivatives
algorithm
Partial derivatives algorithm
Berry-Sethi algorithm
Followers algorithm
Finite
automata
Automata determination.
Informática (Informática)
1203.17 Informática
Trabajo de Fin de Grado Ingería Informática, Facultad de Informática UCM, Departamento de Ingeniería del Software e Inteligencia Artificial, Curso 2020/2021, el código de esta herramienta está disponible en el repositorio de GitHub:
https://github.com/7216nat/TFG_Comprobador-de-equivalencia-entre-especificaciones-
basadas-en-expresiones-regulares
En este trabajo, realizamos un estudio sobre los diferentes algoritmos necesarios (y algunas alternativas) en la comprobación de equivalencia entre dos expresiones regulares, con todos los pasos que ello implica: creación de autómatas finitos, determinación de aquellos que lo necesiten y comprobación de la equivalencia.
El trabajo culmina con la creación y pruebas de una herramienta que admite dos especificaciones basadas en expresiones regulares y permite hacer comparaciones entre ellas, de manera total o parcial, utilizando los diferentes algoritmos de comprobación de la equivalencia entre expresiones regulares implementados.
In this work, we study the different algorithms needed (and some alternatives) for checking the equivalence of two regular expressions, with all the steps involved: creation of finite automata, determination of those that require it and equivalence checking between the
resulting deterministic automata.
The work will finish with the creation and testing of a tool that can receive two regular expression-based specifications and makes it possible to compare them, partially or completely, with the help of the different algorithms for checking the equivalency of regular expressions.
Depto. de Ingeniería de Software e Inteligencia Artificial (ISIA)
Fac. de Informática
TRUE
unpub
2023-06-17T10:54:06Z
2023-06-17T10:54:06Z
2021
bachelor thesis
https://hdl.handle.net/20.500.14352/10434
XXXX-XXXX
spa
Atribución-NoComercial 3.0 España
https://creativecommons.org/licenses/by-nc/3.0/es/
open access
application/pdf