Prueba de intersección de dos idiomas regulares

Quiero probar si dos idiomas tienen una cadena en común. Ambos idiomas provienen de un subconjunto de los idiomas regulares que se describen a continuación y solo necesito saber si existe una cadena en ambos idiomas, no producir una cadena de ejemplo.Prueba de intersección de dos idiomas regulares

El lenguaje es especificado por una cadena Glob-como como

/foo/**/bar/*.baz

donde ** 0 o más de los personajes y * partidos cero o más caracteres que no son /, y todos otros personajes son literales.

¿Alguna idea?

gracias, micrófono

EDIT:

I implementado algo que parece funcionar bien, pero aún tienen que probar una prueba de corrección. Se puede ver la source y unit tests

Fuente

2010-02-26 Mike Samuel

¿Qué idioma utilizará para realizar el control? Probablemente va a necesitar escribir una cama de prueba para esto. Si pudieras publicar un banco de pruebas bastante completo, sería útil. –

Esto deberá ejecutarse en JS. Por supuesto, tendré que escribir un testbed. Encontré un subconjunto útil para el cual puedo calcular la intersección de manera eficiente haciendo algunos trucos. El subconjunto útil es aquel en el que * y ** solo pueden aparecer al principio o directamente después de a /, y a/no puede ser adyacente a otro /. Eso significa que nunca tengo que preocuparme de si * foo * puede coincidir con boo * baz - Tengo que hacer un backtracking, pero no es una cantidad ridícula ya que siempre puedo convertir el texto después de un * o ** en una comprobación de sufijo. –

Construir AF A y B para ambos idiomas, y la construcción de la "intersección FA" AnB. Si AnB tiene al menos un estado de aceptación accesible desde el estado de inicio, entonces hay una palabra que está en ambos idiomas.

Construir AnB podría ser complicado, pero estoy seguro de que hay libros de texto de FA que lo cubren. El enfoque me gustaría tener es:

Los estados de AnB es el producto cartesiano de los estados de A y B respectivamente. Un estado en AnB se escribe (a, b) donde a es un estado en A y b es un estado en B.
Una transición (a, b) ->r (c, d) (es decir, hay una transición (a, b)-(c, d) en símbolo r) existe si y sólo si a ->r c es una transición en A, y b ->r d es una transición en B.
(a, b) es un estado de inicio en AnB si y sólo si a y b son comenzar estados en A y B respectivamente.
(a, b) es un estado de aceptación en AnB iff cada uno es un estado de aceptación en su FA respectivo.

¡Todo esto está fuera de mi cabeza, y por lo tanto completamente sin probar!

Fuente

2010-02-26 01:32:28 Edmund

Bueno, esta es una construcción bien documentada llamada Máquina de Producto Cartesiana, muchas personas lo vencerán a esto, y es un método bien documentado y correcto para obtener un FA reconociendo la intersección de idiomas reconocidos por otros FA. Solo digo. – Patrick87

Acabo de hacer una búsqueda rápida y este problema es decidible (también conocido como se puede hacer), pero no conozco ningún buen algoritmo para hacerlo. Uno está solución es:

Convierte tanto regulares expresiones a NFA A y B
Crear un NFA, C, que representa la intersección de A y B.
Ahora intente cada cadena de 0 a la cantidad de estados en C y vea si C lo acepta (ya que si la cadena es más larga, debe repetir estados en un punto).

Sé que esto podría ser un poco difícil de seguir, pero esta es la única manera que sé cómo hacerlo.

Fuente

2010-02-26 02:00:43 Bishnu

Prueba de intersección de dos idiomas regulares

Respuesta

Cuestiones relacionadas