Czy istnieje algorytm, który może wytworzyć wyrażenie regularne (może ograniczone do uproszczonej gramatyki) ze zbioru ciągów znaków, tak że ocena wszystkich możliwych ciągów pasujących do wyrażenia regularnego odtwarza początkowy zestaw ciągów?

Prawdopodobnie nierealistyczne jest znalezienie takiego algorytmu dla gramatyk wyrażeń regularnych o bardzo „skomplikowanej” składni (w tym dowolnych powtórzeń, twierdzeń itp.), Więc zacznijmy od uproszczonego, który dopuszcza tylkoOR podciągów:

foo(a|b|cd)bar powinno pasowaćfooabar, foobbar ifoocdbar.

Przykłady

Biorąc pod uwagę zestaw ciągówh_q1_a, h_q1_b, h_q1_c, h_p2_a, h_p2_b, h_p2_c, pożądanym wyjściem algorytmu byłobyh_(q1|p2)_(a|b|c).

Biorąc pod uwagę zestaw ciągówh_q1_a, h_q1_b, h_p2_a, pożądanym wyjściem algorytmu byłobyh_(q1_(a|b)|p2_a). Zauważ, żeh_(q1|p2)_(a|b) by niebądź poprawny, ponieważ rozszerza się do 4 ciągów, w tymh_p2_b, którego nie było w oryginalnym zestawie ciągów.

Przypadek użycia

Mam długą listę etykiet, które zostały wyprodukowane przez złożenie podciągów. Zamiast drukować ogromną listę ciągów, chciałbym mieć kompaktowe wyjście wskazujące, które etykiety znajdują się na liście. Ponieważ pełna lista została stworzona programowo (przy użyciu skończonego zbioru pre- i przyrostków), oczekuję, że notacja kompaktowa będzie (potencjalnie) znacznie krótsza niż lista początkowa.

((Uproszczony) regex powinien być jak najkrótszy, chociaż bardziej interesuje mnie praktyczne rozwiązanie niż najlepsze. Trywialna odpowiedź polega oczywiście na połączeniu wszystkich ciągów, takich jak A | B | C | D | ... które nie jest jednak pomocne.)