Expresiones regulares mutuamente excluyentes

Question

Si tengo una lista de expresiones regulares, ¿hay alguna manera fácil de determinar que ninguna de ellas devolverá una coincidencia para la misma cadena?

Es decir, la lista es válida si, y solo si, para todas las cadenas, un máximo de un elemento de la lista coincidirá con la cadena completa.

Parece que esto será muy difícil (¿quizás imposible?) Para demostrarlo definitivamente, pero parece que no puedo encontrar ningún trabajo sobre el tema.

La razón por la que pregunto es que estoy trabajando en un tokenizador que acepta expresiones regulares, y me gustaría asegurar que solo un token a la vez pueda coincidir con el encabezado de la entrada.

Answer 1

Si está trabajando con expresiones regulares puras (sin referencias ni otras características que hagan que reconozcan lenguajes sin contexto o más complicados), lo que pregunte es posible. Lo que puede hacer es convertir cada expresión regular en DFA, luego (dado que los idiomas normales se cierran en intersección) combinarlos en un DFA que reconozca la intersección de los dos idiomas. Si ese DFA tiene una ruta desde el estado de inicio hasta un estado de aceptación, ambas cadenas regexen de entrada aceptan esa cadena.

El problema con esto es que el primer paso del algoritmo DGE regex-> habitual es convertir la expresión regular en un NFA, luego convertir el NFA en un DFA. Pero ese último paso puede dar como resultado una explosión exponencial en el número de estados de DFA, por lo que solo será factible para expresiones regulares muy simples.

Si está trabajando con la sintaxis de expresiones regulares extendidas, todas las apuestas están desactivadas: los idiomas sin contexto no están cerrados en la intersección, por lo que este método no funcionará.

Answer 2

El Wkipedia article on regular expressions hace estado

Es posible escribir un algoritmo que para dos expresiones regulares dadas decide si los idiomas descritos son esencialmente iguales, reduce cada expresión a una máquina de estado finito determinista mínima, y ​​determina si son isomorfos (equivalentes)

pero no da más pistas.

Por supuesto, lo más fácil que puede hacer es realizar muchas pruebas, pero todos sabemos las deficiencias de las pruebas como método de prueba.

Answer 3

No puede hacer eso solo mirando la expresión regular.

Considere el caso en el que tiene [0-9] y [0-9]+. Obviamente son expresiones diferentes, pero cuando se aplican a la cadena "1", ambas producen el mismo resultado. Cuando se aplica a la cadena "11" producen diferentes resultados.

El punto es que una expresión regular no es suficiente información. El resultado depende tanto de la expresión regular como de la cadena de destino.