Czy istnieje algorytm, który może ustalić, czy jeden język regularny pasuje do dowolnego wejścia, który odpowiada innym regularnym dopasowaniom językowym?

Powiedzmy mamy wyrażeń regularnych:..Czy istnieje algorytm, który może ustalić, czy jeden język regularny pasuje do dowolnego wejścia, który odpowiada innym regularnym dopasowaniom językowym?

Witam W. * RLD
Witam Świata
* Świat
* W. *

chciałbym zminimalizować liczba wyrażeń wymaganych do dopasowania arbitralnych danych wejściowych.

Aby to zrobić, muszę sprawdzić, czy jedno wyrażenie regularne pasuje do danych wejściowych dopasowanych przez inne wyrażenie. Czy to jest możliwe?

Billy3

Źródło

2010-09-02 Billy ONeal

@skaffman: Myślę, że znacznik języka regularnego jest odpowiedni, biorąc pod uwagę, że wyrażenie regularne opisuje zwykły język - jest to po prostu prosty sposób przedstawienia go "na papierze". Ale pytanie w.r.t. informatyka ma więcej wspólnego z normalnymi językami niż wyrażeń regularnych. –

eh, tytuł nie pasuje do opisu? – maxschlepzig

Nie jestem pewien, czy kwalifikuje się jako "algorytm", ale używając ". *" Dopasowuje dowolne dane wejściowe z jednym wyrażeniem regularnym; Wątpię, czy można go zminimalizować do mniej niż 1. :-) –

Każde wyrażenie regularne można połączyć z DFA - możesz zminimalizować DFA, a ponieważ minimalna forma jest unikatowa, możesz zdecydować, czy dwa wyrażenia są równoważne. Dani Cricco wskazał algorytm Hopcroft O (n log n). Istnieje jeszcze jeden ulepszony algorytm Hopcroft i Craft, który testuje równoważność dwóch DFA w O (n).

Dla dobrego badania w tej sprawie i interesującego podejścia do tego, polecam papier Testing the Equivalence of Regular Languages, z arXiv.

Późniejsza edycja: jeśli interesujesz się włączeniem zamiast równoważności dla wyrażeń regularnych, natknąłem się na artykuł, który może być interesujący: Inclusion Problem for Regular Expressions - Przeszukałem go tylko, ale wydaje się, że zawiera on algorytm wielomianowy do problem.

Źródło

2010-09-02 19:31:59 Lawrence

Hmmm .. interesujące. Jedną z kwestii jest jednak to, że '. *' I 'Hello World' są zdecydowanie odmienne, chociaż'. * 'Może pasować do wszystkiego, co można porównać z' Hello World'. –

Nie jestem pewien co do znaczenia "dopasowania" do ciebie - wydaje się, że nie chcesz testować równoważności, ale raczej włączenia. Czy możesz dokładniej odpowiedzieć na pytanie? – Lawrence

Moja trudność polega na tym, że nie wiem dokładnie, jak opisać to, czego szukam - przepraszam za omijanie tutaj. Lekko zmodyfikowałem pytanie - z opisu Wikipedii na temat teorii teorii mnóstwa wydaje mi się, czego potrzebuję. –

Tak.

Problem równoważności dwóch języków regularnych jest rozstrzygalny.

Szkic algorytmu:

zminimalizować zarówno sprawdzanie DFAS
jeśli są isomorph

Źródło

2010-09-02 19:12:25 maxschlepzig

Izomorfizmem wykresu nie da się rozwiązać w czasie wielomianowym, więc nie widzę, jak to pomaga. –

@Billy: Sądzę, że twoja odpowiedź jest taka, że jest to teoretycznie rozwiązalny problem, który nie jest praktyczny do rozwiązania. – szbalint

@szbalint: Cóż "teoretycznie" mógłbym przedstawić każdy możliwy ciąg wejściowy dla języków i sprawdzić, czy pasują do tego samego. Jeśli nie można go rozwiązać na rozsądnym sprzęcie konsumenckim, nie ma sensu. –

Pewnie !. Wyrażenie regularne może być reprezentowane jako FSM (Finite State Machine) i istnieje technicznie nieskończona liczba FSM, które mogą rozpoznać ten sam ciąg.

Izomorfizm to nazwa opisująca, czy dwa FSM są równoważne. Istnieje kilka algorytmów, aby zminimalizować FSM. Na przykład Hopcroft minimization algorithm może zminimalizować dwa FSM w O (n log n), w automatie n-stanowym.

Źródło

2010-09-02 19:18:07

@Dani: Ten sam problem z odpowiedzią maxschlepziga. Izomorfizm jest w klasie NP. –

@Billy ONeal: Po pierwsze, (wykres) izomorfizm jest w NP (to prawda), ale uważa się, że nie jest NP-zupełny, chociaż nie w P. Jednak mówimy o izomorfizmie DFA, który jest zupełnie inny. – jpalecek

@jpalecek: Czym różni się izomorfizm DFA? Czy DFA to nic innego jak dwuznak? –

Ten problem nazywa się "włączeniem" lub "subsuma" wyrażeń regularnych, ponieważ to, o co prosisz, to czy zestaw słów dopasowanych przez jedno wyrażenie regularne zawiera (lub podsieci) zestaw słów dopasowanych przez inne wyrażenie . Równość to inne pytanie, które zwykle oznacza, czy dwa wyrazy regularne dopasowują dokładnie te same słowa, to znaczy, że są funkcjonalnie równoważne. Na przykład "a *" zawiera "aa *", podczas gdy nie są one równe.

Wszystkie znane algorytmy włączania wyrażeń regularnych są najgorszym przypadkiem, gdy czas eksponencjalny wpływa na rozmiar wyrażeń regularnych.Ale średnia algorytm jest tak:

R1 Wejście i R2 Wyjście Tak, jeśli R1 zawiera r2

Tworzenie DFA (R1) i DFA (r2)
Tworzenie Neg (DFA (R1)) (który pasuje dokładnie do słów r1 dont match)
Utwórz Neg (DFA (r1)) x DFA (r2) (który pasuje dokładnie do słów dopasowanych przez Neg (DFA (r1)) i DFA (r2))
Sprawdź, czy automat wykonany w wersji 3. nie pasuje do żadnego słowa

Działa to, ponieważ sprawdzane jest to, że nie ma słów dopasowanych przez r2, które nie są dopasowane przez r1.

Źródło

2015-11-30 11:58:22 Dag

Czy istnieje algorytm, który może ustalić, czy jeden język regularny pasuje do dowolnego wejścia, który odpowiada innym regularnym dopasowaniom językowym?

Odpowiedz

Powiązane problemy