¿Existe un algoritmo que pueda producir una expresión regular (tal vez limitada a una gramática simplificada) a partir de un conjunto de cadenas de modo que la evaluación de todas las cadenas posibles que coincidan con la expresión regular reproduzca el conjunto inicial de cadenas?

Probablemente no sea realista encontrar un algoritmo de este tipo para las gramáticas de expresiones regulares con una sintaxis muy "complicada" (incluyendo repeticiones arbitrarias, aserciones, etc.), así que comencemos con una simplificada que solo permite unaOR de subcadenas:

foo(a|b|cd)bar debe coincidirfooabar, foobbar yfoocdbar.

Ejemplos

Dado el conjunto de cuerdash_q1_a, h_q1_b, h_q1_c, h_p2_a, h_p2_b, h_p2_c, la salida deseada del algoritmo seríah_(q1|p2)_(a|b|c).

Dado el conjunto de cuerdash_q1_a, h_q1_b, h_p2_a, la salida deseada del algoritmo seríah_(q1_(a|b)|p2_a). Tenga en cuenta queh_(q1|p2)_(a|b) haría noser correcto porque eso se expande a 4 cuerdas, incluyendoh_p2_b, que no estaba en el conjunto original de cuerdas.

Caso de uso

Tengo una larga lista de etiquetas que fueron producidas al juntar subcadenas. En lugar de imprimir la amplia lista de cadenas, me gustaría tener una salida compacta que indique qué etiquetas están en la lista. Como la lista completa se ha producido mediante programación (utilizando un conjunto finito de pre y sufijos) espero que la notación compacta sea (potencialmente) mucho más corta que la lista inicial.

(La expresión regular (simplificada) debe ser lo más corta posible, aunque estoy más interesado en una solución práctica que en la mejor. La respuesta trivial es, por supuesto, simplemente concatenar todas las cadenas como A | B | C | D | ... que es, sin embargo, no es útil.)