¿Existe un algoritmo que puede determinar si un idioma regular coincide con cualquier entrada que coincida con el idioma normal?

Digamos que tenemos expresiones regulares:..¿Existe un algoritmo que puede determinar si un idioma regular coincide con cualquier entrada que coincida con el idioma normal?

Hola W. * RLD
Hola mundo
* Mundial
* * W.

me gustaría minimizar el número de expresiones regulares necesarias para hacer coincidir la entrada arbitraria.

Para hacer eso, necesito encontrar si una expresión regular coincide con ninguna entrada igualada por otra expresión. ¿Es eso posible?

Billy3

Fuente

2010-09-02 Billy ONeal

@skaffman: Creo que la etiqueta de idioma normal es apropiada, dado que una expresión regular describe un idioma normal, es solo una manera simple de representarlo "en papel". Pero la pregunta w.r.t. la informática tiene más que ver con los lenguajes regulares que las expresiones regulares. –

eh, el título no coincide con la descripción? – maxschlepzig

No estoy seguro si califica como un "algoritmo", pero usar ". *" Coincide con la entrada arbitraria con una expresión regular; Dudo que se pueda minimizar a menos de 1. :-) –

Cualquier expresión regular puede vincularse a un DFA - se puede minimizar el DFA y dado que la forma mínima es único, puede decidir si dos expresiones son equivalentes. Dani Cricco señaló el algoritmo Hopcroft O (n log n). Hay otro algoritmo mejorado por Hopcroft y Craft que prueba la equivalencia de dos DFA en O (n).

Para una buena encuesta sobre el tema y un enfoque interesante para esto, recomiendo el documento Testing the Equivalence of Regular Languages, de arXiv.

Edición posterior: si está interesado en la inclusión en lugar de la equivalencia para las expresiones regulares, me he topado con un documento que podría ser de interés: Inclusion Problem for Regular Expressions - Solo lo he examinado pero parece contener un algoritmo de tiempo polinomial el problema.

Fuente

2010-09-02 19:31:59 Lawrence

Hmmm .. interesante. Sin embargo, un problema es que '. *' Y 'Hello World' son decididamente no equivalentes, aunque'. * 'Puede coincidir con cualquier cosa' Hello World' puede coincidir. –

No estoy seguro del significado de "coincidencia" para usted; parece que no desea probar la equivalencia sino la inclusión. ¿Puedes ser más exacto con tu pregunta? – Lawrence

Mi dificultad es que no sé exactamente cómo describir lo que estoy buscando, lo siento por la confusión aquí. He modificado ligeramente la pregunta, de la descripción de Wikipedia sobre la inclusión de la teoría de conjuntos parece ser lo que necesito. –

Sí.

El problema de la equivalencia de dos lenguajes regulares es decidible.

Bosquejo de un algoritmo:

minimizar el registro de entrada DFA
si son isomorfo

Fuente

2010-09-02 19:12:25 maxschlepzig

El isomorfismo gráfico no se puede resolver en tiempo polinomial, por lo que no veo cómo eso ayuda. –

@Billy: supongo que su respuesta es que este es un problema teóricamente solucionable que no es práctico de resolver. – szbalint

@szbalint: Bueno "teóricamente" podría representar todas las cadenas de entrada posibles a los idiomas y ver si coinciden con lo mismo. Si no se puede resolver con un hardware de consumo razonable, entonces no tiene mucho sentido. –

Claro !. Una expresión regular se puede representar como un FSM (Máquina de estados finitos) y hay un número técnicamente infinito de FSM que puede reconocer la misma cadena.

isomorfismo es el nombre que describe si dos FSM son equivalentes. Hay un par de algoritmos para minimizar un FSM. Por ejemplo, el Hopcroft minimization algorithm puede minimizar dos FSM en O (n log n), en un autómata de n estados.

Fuente

2010-09-02 19:18:07

@Dani: Mismo problema con la respuesta de maxschlepzig. El isomorfismo está en la clase NP. –

@Billy ONeal: Primero, el isomorfismo (gráfico) está en NP (es cierto), pero se cree que no es NP completo, aunque no en P. Sin embargo, estamos hablando del isomorfismo de DFA, que es una cosa completamente diferente. – jpalecek

@jpalecek: ¿En qué se diferencia el isomorfismo de DFA? ¿Es un DFA nada más que un dígrafo? –

Este problema se denomina "inclusión" o "subsunción" de expresiones regulares, porque lo que está pidiendo es si el conjunto de palabras con una expresión regular incluye (o subsume) el conjunto de palabras con la otra expresión regular . La igualdad es una pregunta diferente que normalmente significa si dos expresiones regulares coinciden exactamente con las mismas palabras, es decir, que son funcionalmente equivalentes. Por ejemplo, "a *" incluye "aa *", mientras que no son iguales.

Todos los algoritmos conocidos para la inclusión de expresiones regulares son el peor de los casos toma tiempo exponencial en el tamaño de la expresión regular.Sin embargo, el algoritmo estándar es la siguiente:

r1 de entrada y r2 salida Sí si R1 incluye r2

Crear DFA (r1) y DFA (r2)
Crear Neg (DFA (r1)) (que coincide exactamente con esas palabras r1 no coinciden)
Crear Neg (DFA (r1)) x DFA (R2) (que coincide exactamente con esas palabras coincidentes por Neg (DFA (r1)) y DFA (r2))
Compruebe que el autómata hecho en 3. no coincide con ninguna palabra

Esto funciona, ya que lo que está revisando es que no hay palabras emparejadas por r2 que no coincidan con r1.

Fuente

2015-11-30 11:58:22 Dag

¿Existe un algoritmo que puede determinar si un idioma regular coincide con cualquier entrada que coincida con el idioma normal?

Respuesta

Cuestiones relacionadas