expresión regular "contiene" otra expresión regular

¿Hay alguna manera de comprobar si una expresión regular "contiene" otra expresión regular?
Por ejemplo:
expresión regular "contiene" otra expresión regular

RegEX1 = "a.*b"; 
RegEx2 = "a1.*b";

RegEX1 "contiene" RegEX2.

Por lo que yo sé, esto no se puede hacer, ¿estoy equivocado?

OK, joel.neely ha demostrado que se puede hacer (no lo he leído aún ...) académicamente.

¿Se puede hacer en un lenguaje de programación, digamos C#?
¿Qué tan efectivo será eso? ¿Cuánto tiempo tomará probar 1000 pares?

Fuente

2009-01-06 Dror

Sí.

This paper contiene una discusión detallada del tema (ver sección 4.4).

Fuente

2009-01-06 13:20:29

Puede aclarar su "sí". Creo que estás diciendo "Sí, estás equivocado" y citando el documento que muestra cómo se puede hacer (a partir de un vistazo rápido al documento). Pero valdría la pena deletrear eso explícitamente. –

El documento mencionado solo dice "Es un resultado bien conocido que para dos expresiones regulares B y R, es fácil decidir si B subsume R" y luego pasa a describir "modelos de contenido". Además, el método del artículo parece simplemente enumerar todas las cadenas con length Clueless

Aceptado aunque no de manera práctica para lograr ... – Dror

La conversión de las dos expresiones a las máquinas de estado equivalentes, y la comprobación de todas las rutas en ambas máquinas permiten las mismas coincidencias, debería hacer el truco. La cantidad de bombeo obviamente debe tener en cuenta, así que evite volver a visitar los nodos antiguos.

Solo funcionaría para las expresiones regulares "simples" (o reales, lo que tiene, las expresiones recursivas perls son mucho más expresivas).

Mientras que un gráfico de la máquina de estado podría tener un gran número de rutas, aún así debería ser limitado (especialmente si la fuente para las expresiones son humanas). De modo que encontraría todas las rutas permitidas de RegEX1, y verificaría, una por una, si está permitido en RegEX2. Si todas las rutas son válidas, sabrá que una está contenida en la otra.

Fuente

2009-06-10 12:41:52 Svend

¿Es posible (en un tiempo razonable) ejecutar una prueba para obtener una jerarquía de expresión regular (varios cientos de ellos)? ¿Puedes proporcionar punteros al código que haga eso? – Dror

No veo por qué no sería posible, y en tiempo decente también. Sin embargo, tendrías que construir esto desde cero, lo cual no es trivial. – Svend

comprobar que "todas las rutas son válidas" para todos los pares probablemente tomaría un tiempo muy largo. "verificando todos los caminos en ambas máquinas" como dices puede ser infinito, ¿o me falta algo? – Dror

expresión regular "contiene" otra expresión regular

Respuesta

Cuestiones relacionadas