regex - regulares - ¿Cómo determinar si una expresión regular es ortogonal a otra expresión regular?

javascript regex test

Question

Supongo que mi pregunta se explica mejor con un ejemplo (simplificado).

Regex 1:

^/d+_[a-z]+$

Regex 2:

^/d*$

Regex 1 nunca coincidirá con una cadena donde corresponda Regex 2. Entonces digamos que regex 1 es ortogonal a regex 2.

Como mucha gente me preguntó a qué me refería por ortogonal , trataré de aclararlo:

Deje que S1 sea ​​el conjunto (infinito) de cadenas donde coincida la expresión regular 1. S2 es el conjunto de cadenas donde coincide la expresión regular 2. Regex 2 es ortogonal a regex 1 si la intersección de S1 y S2 está vacía. La expresión regular ^ / d_a $ no sería ortogonal, ya que la cadena ''2_a'' está en el conjunto S1 y S2.

¿Cómo puede determinarse programáticamente si dos expresiones regulares son ortogonales entre sí?

El mejor caso sería una biblioteca que implementa un método como:

/**
* @return True if the regex is orthogonal (i.e. "intersection is empty"), False otherwise or Null if it can''t be determined
*/
public Boolean isRegexOrthogonal(Pattern regex1, Pattern regex2);

Answer 1

Este parece ser un uso diferente de la palabra ortogonal a la que estoy acostumbrado.

¿Consideras dos RE ortogonales si se superponen de alguna manera? ¿O si uno es un subconjunto del otro? ¿O simplemente si no se pueden usar para unir el mismo texto?

Si es el último, entonces puede usar el hecho de que cualquier RE se puede traducir a una máquina de estados finitos. Dos máquinas de estado finito son iguales si tienen el mismo conjunto de nodos, con los mismos arcos conectando esos nodos.

Entonces, dado lo que creo que está usando como definición para ortogonal, si traduce sus RE en FSM y esas FSM no son iguales, las RE son ortogonales.

Answer 2

Permítanme comenzar diciendo que no tengo idea de cómo construir dicho algoritmo, ni conozco ninguna biblioteca que lo implemente. Sin embargo, no me sorprendería en absoluto saber que ninguno existe para las expresiones regulares generales de complejidad arbitraria.

Cada expresión regular define un lenguaje regular de todas las cadenas que puede generar la expresión, o si lo prefiere, de todas las cadenas que "coinciden" con la expresión regular. Piense en el lenguaje como un conjunto de cadenas. En la mayoría de los casos, el conjunto será infinitamente grande. Su pregunta se pregunta si las intersecciones de los dos conjuntos dados por las expresiones regulares están vacías o no.

Al menos en una primera aproximación, no puedo imaginar una manera de responder esa pregunta sin calcular los conjuntos, que para conjuntos infinitos tomarán más tiempo del que tienes. Creo que podría haber una manera de calcular un conjunto limitado y determinar cuándo se está elaborando un patrón más allá de lo que requiere la otra expresión regular, pero no sería sencillo.

Por ejemplo, solo considere las expresiones simples (ab)* y (aba)*b . ¿Cuál es el algoritmo que decidirá generar abab partir de la primera expresión y luego detenerse, sin verificar ababab , abababab , etc. porque nunca funcionarán? No puede simplemente generar cadenas y verificar hasta encontrar una coincidencia porque eso nunca se completará cuando los idiomas sean disjuntos. No puedo imaginar nada que funcione en el caso general, pero luego hay gente mucho mejor que yo en este tipo de cosas.

En general, este es un problema difícil. Me sorprendería saber que hay una solución de tiempo polinomial, y no me sorprendería en absoluto saber que es equivalente al problema de detenerse. Aunque, dado que las expresiones regulares no están completas, al menos parece posible que exista una solución.

Answer 3

Por "ortogonal" te refieres a "la intersección es el conjunto vacío" ¿Lo tomo?

Construiría la expresión regular para la intersección, luego convertiría a una gramática normal en forma normal, y vería si es el lenguaje vacío ...

Por otra parte, soy un teórico ...

Answer 4

Probar que una expresión regular es ortogonal a otra puede ser trivial en algunos casos, como grupos de caracteres mutuamente excluyentes en las mismas ubicaciones. Para cualquiera menos las expresiones regulares más simples, este es un problema no trivial. Para expresiones serias, con grupos y referencias, iría tan lejos como para decir que esto puede ser imposible.

Answer 5

Quizás pueda usar algo como Regexp :: Genex para generar cadenas de prueba para que coincida con una expresión regular específica y luego use la cadena de prueba en la segunda expresión regular para determinar si las 2 expresiones regulares son ortogonales.

Answer 6

Yo haría lo siguiente:

• convierta cada expresión regular a una FSA, utilizando algo así como la siguiente estructura:

  struct FSANode
  {
  bool accept;
  Map<char, FSANode> links;
  }
  List<FSANode> nodes;
  FSANode start;

Tenga en cuenta que esto no es trivial, pero para regex simple no debería ser tan difícil.

• Crea un nuevo nodo combinado como:

  class CombinedNode
  {
  CombinedNode(FSANode left, FSANode right)
  {
  this.left = left;
  this.right = right;
  }
  Map<char, CombinedNode> links;
  bool valid { get { return !left.accept || !right.accept; } }
  public FSANode left;
  public FSANode right;
  }

Cree enlaces basados ​​en seguir la misma char en los lados izquierdo y derecho, y obtendrá dos FSANodes que forman un nuevo CombinedNode.

Luego comience en CombinedNode (leftStart, rightStart), y encuentre el spanning set, y si hay un CombinedNodes no válido, el conjunto no es "ortogonal".

Answer 7

Construiría la expresión regular para la intersección, luego convertiría a una gramática normal en forma normal, y vería si es el lenguaje vacío ...

Eso parece como disparar a los gorriones con un cañón. ¿Por qué no simplemente construir el producto autómata y verificar si se puede alcanzar un estado de aceptación desde el estado inicial? Eso también te dará una cadena en la intersección de inmediato sin tener que construir una expresión regular primero.

Me sorprendería saber que hay una solución de tiempo polinomial, y no me sorprendería en absoluto saber que es equivalente al problema de detenerse.

Solo sé de una manera de hacerlo que implica crear un DFA a partir de una expresión regular, que es el tiempo exponencial (en el caso degenerado). Es reducible al problema de detención, porque todo lo es, pero el problema de detención no se puede reducir a él .

Si es el último, entonces puede usar el hecho de que cualquier RE se puede traducir a una máquina de estados finitos. Dos máquinas de estado finito son iguales si tienen el mismo conjunto de nodos, con los mismos arcos conectando esos nodos.

Entonces, dado lo que creo que está usando como definición para ortogonal, si traduce sus RE en FSM y esas FSM no son iguales, las RE son ortogonales.

Eso no es correcto Puede tener dos DFA (FSM) que no son isomorfos en el sentido multigrafiado marcado con el borde, pero aceptan los mismos idiomas. Además, si ese no fuera el caso, su prueba verificará si dos expresiones regulares aceptan no idénticas , mientras que OP quiere idiomas que no se solapen (intersección vacía).

Además, tenga en cuenta que la construcción / 1, / 2, ..., / 9 no es regular: no se puede expresar en términos de concatenación, unión y * (estrella de Kleene). Si desea incluir una sustitución de respaldo, no sé cuál es la respuesta. También es de interés el hecho de que el problema correspondiente para los lenguajes sin contexto es indecidible: no existe un algoritmo que tome dos gramáticas libres de contexto G1 y G2 y devuelve verdadero si f L (G1) ∩ L (g2) ≠ Ø.

Answer 8

Convierta cada expresión regular en un DFA. Desde el estado de aceptación de un DFA, cree una transición épsilon al estado de inicio del segundo DFA. De hecho, habrá creado un NFA agregando la transición épsilon. Luego convierta el NFA en un DFA. Si el estado de inicio no es el estado de aceptación, y el estado de aceptación es alcanzable, entonces las dos expresiones regulares no son "ortogonales". (Dado que su intersección no está vacía)

Existen procedimientos conocidos para convertir una expresión regular en un DFA y convertir un NFA en DFA. Puede consultar un libro como "Introducción a la teoría de la computación" de Sipser para ver los procedimientos, o simplemente buscar en la web. Sin duda, muchos estudiantes y graduados tuvieron que hacer esto para una clase de "teoría" u otra.

Answer 9

Hablé demasiado pronto Lo que dije en mi publicación original no funcionaría, pero hay un procedimiento para lo que intenta hacer si puede convertir sus expresiones regulares en formato DFA.

Puede encontrar el procedimiento en el libro que mencioné en mi primera publicación: "Introducción a la teoría de la computación", segunda edición de Sipser. Está en la página 46, con detalles en la nota al pie.

El procedimiento le proporcionará un nuevo DFA que es la intersección de los dos DFA. Si el nuevo DFA tiene un estado de aceptación alcanzable, entonces la intersección no está vacía.

Answer 10

Las fsmtools pueden hacer todo tipo de operaciones en máquinas de estados finitos, su único problema sería convertir la representación de cadenas de la expresión regular en el formato con el que fsmtools puede funcionar. Esto es definitivamente posible para casos simples, pero será complicado en la presencia de funciones avanzadas como look {ahead, behind}.

También puede echarle un vistazo a OpenFst , aunque nunca lo he usado. Sin embargo, admite la intersección.

Answer 11

Excelente punto en el / 1, / 2 bit ... que es libre de contexto, y por lo tanto no se puede resolver. Punto menor: No TODO es reducible a Halt ... Equivalencia de programa, por ejemplo .. - Brian Postow

[Estoy respondiendo a un comentario]

IIRC, a^nb^ma^nb^m no está libre de contexto, por lo que (a/*)(b/*)/1/2 tampoco lo es porque es lo mismo. ISTR { ww | w ∈ L } { ww | w ∈ L } no ser "agradable", incluso si L es "agradable", para ser agradable uno de regular , sin context-free .

Modifico mi declaración: todo en RE es reducible al problema de detención ;-)

Answer 12

Han pasado dos años desde que se publicó esta pregunta, pero me complace decir que esto se puede determinar ahora simplemente llamando al programa "genex" aquí: https://github.com/audreyt/regex-genex

$ ./binaries/osx/genex ''^/d+_[a-z]+$'' ''^/d*$''
$

La salida vacía significa que no hay cadenas que coincidan con ambas expresiones regulares. Si tienen alguna superposición, mostrará la lista completa de superposiciones:

$ runghc Main.hs ''/d'' ''[123abc]''
1.00000000 "2"
1.00000000 "3"
1.00000000 "1"

¡Espero que esto ayude!

Answer 13

Finalmente encontré exactamente la biblioteca que estaba buscando:

dk.brics.automaton

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();
}

Cabe señalar que la implementación no admite ni puede admitir funciones complejas de RegEx, como referencias anteriores. Vea la publicación del blog "A Reaster Java Regex Package" que presenta dk.brics.automaton .

Answer 14

Creo que kdgregory es correcto, estás usando Ortogonal para significar Complemento .

¿Es esto correcto?