Intersección de dos expresiones regulares

Question

Estoy buscando la función (PHP será el mejor), que devuelve verdadero si la cadena existente coincide tanto con regexpA como con regexpB.

Ejemplo 1:

$regexpA = '[0-9]+'; 
$regexpB = '[0-9]{2,3}'; 

hasRegularsIntersection($regexpA,$regexpB) vuelve TRUE porque '12' partidos ambos regexps

Ejemplo 2:

$regexpA = '[0-9]+'; 
$regexpB = '[a-z]+'; 

hasRegularsIntersection($regexpA,$regexpB) devuelve falso porque los números no partidos literales.

Gracias por cualquier sugerencia sobre cómo solucionar esto.

Henry

Answer 1

Es posible. Lo encontré una vez con el razonador de Pellet OWL mientras aprendía tecnologías web semánticas.

Here is an example que muestra cómo las expresiones regulares se pueden analizar en una estructura de árbol. A continuación, podría (en teoría) analizar sus dos expresiones regulares en árboles y ver si un árbol es un subconjunto del otro árbol, es decir. si un árbol se puede encontrar dentro de los nodos de otros árboles.

Si se encuentra, la otra expresión regular coincidirá (no solo, sino también) con un subconjunto de lo que coincidirá con la primera expresión regular.

No es una gran solución, pero tal vez te ayude.

Answer 2

Para expresiones regulares que son realmente regular (es decir, no utilizan características irregulares como referencias anteriores) se puede hacer lo siguiente:

1. transformar el regexen en autómatas finitos (el algoritmo para que se puede encontrar here (capítulo 9) por ejemplo).
2. Construya la intersección del autómata (Usted tiene un estado para cada estado en el producto cartesiano de los estados de los dos autómatas. Luego realiza la transición entre los estados según las reglas de transición del autómata original. Por ejemplo, si se encuentra en estado x1y2, obtienes la entrada a, el primer autómata tiene una transición x1-> x4 para la entrada xy el segundo autómata tiene y2-> y3, pasas al estado x4y3).
3. Compruebe si hay una ruta desde el estado de inicio hasta el estado final en el nuevo autómata. Si existe, los dos regexen se cruzan, de lo contrario no lo hacen.

Answer 3

Una expresión regular especifica una máquina de estados finitos que puede reconocer un conjunto de cadenas potencialmente infinito. El conjunto de cadenas puede ser infinito, pero el número de estados debe ser finito, por lo que puede examinar los estados uno a uno.

Tomando su segundo ejemplo: en la primera expresión, para pasar del estado 0 al estado 1, la cadena debe comenzar con un dígito. En la segunda expresión, para pasar del estado 0 al estado 1, la cadena debe comenzar con una letra. Entonces sabes que no hay ninguna cadena que te lleve del estado 0 al estado 1 en AMBAS expresiones. Usted tiene la respuesta.

Tomando el primer ejemplo: Usted sabe que si la cadena comienza con un dígito, puede pasar del estado 0 al estado 1 con cualquier expresión regular.Así que ahora puede eliminar el estado 0 para cada uno, y simplemente responder la pregunta para cada una de las dos (ahora un estado más pequeño) máquinas de estados finitos.

Esto se parece mucho al conocido "problema de detención" que, como saben, no puede resolverse en el caso general de una máquina de Turing o equivalente. Pero, de hecho, el problema de detención ES solucionable para una máquina de estado finito, simplemente porque hay un número finito de estados.

Creo que podría resolver esto con un FSM no determinista. Si tu expresión regular tuvo solo una transición de cada estado al siguiente, un FSM determinista podría resolverlo. Pero una expresión regular significa que, por ejemplo, si estás en el estado 2, entonces si el caracter es un dígito, vas al estado 3, de lo contrario, si el personaje es una letra, vas al estado 4.

Así que esto es lo que haría hacer:

1. solucionarlo para el subconjunto de EFM de que sólo tienen una transición de un estado a otro. Por ejemplo, una expresión regular que coincida con "Bob" y "bob", y una segunda expresión regular que coincida solo con "bob" y "boB".

2. Vea si puede implementar la solución en una máquina de estados finitos. Creo que esto debería ser posible. La entrada a un estado es un par que representa una transición para un FSM y una transición para el segundo. Por ejemplo: Estado 0: Si (r1, r2) es (("B" o "b"), "b") entonces Estado 1. Estado 1: Si (r1, r2) es (("o"), ("o")) luego state 2. etc.

3. Ahora, para el caso más general, donde por ejemplo el estado dos vuelve al estado dos o un estado anterior; por ejemplo, regex 1 solo reconoce "meet" pero regex 2 reconoce "meeeet" con un número ilimitado de e. Tendría que reducirlos a regex 1 reconociendo "t" y regex 2 reconociendo "t". Creo que esto puede ser solucionado por un FSM no determinista.

Esa es mi intuición de todos modos.

No creo que sea NP-completo, solo porque mi intuición me dice que debería ser capaz de acortar cada regex en un estado en cada paso.

Answer 4

Theory.

Java library.

Uso:

/** 
* @return true if the two regexes will never both match a given string 
*/ 
public boolean isRegexOrthogonal(String regex1, String regex2) { 
    Automaton automaton1 = new RegExp(regex1).toAutomaton(); 
    Automaton automaton2 = new RegExp(regex2).toAutomaton(); 
    return automaton1.intersection(automaton2).isEmpty(); 
}