Algorytm określający, czy dwa wyrażenia regularne są równoważne

Biorąc pod uwagę dwa dowolne wyrażenia regularne, czy istnieje „wydajny” algorytm do ustalenia, czy pasują one do tego samego zestawu ciągów?

Mówiąc bardziej ogólnie, czy możemy obliczyć rozmiar przecięcia dwóch zestawów dopasowań?

W jakich algorytmach można to zrobić i w jakiej klasie złożoności żyją?

Jeśli odrzucimy gwiazdę Kleene, czy to w ogóle zmieni obraz?

algorithms regular-expressions MathematicalOrchid
źródło

Co rozumiesz przez „rozmiar skrzyżowania”? W najciekawszych przypadkach będzie nieskończenie duży; jesteś zainteresowany rozmiarami wrt

Σ^{n}

$\Sigma^n$

Raphael

@Raphael Rozumiem, że wyeliminowanie gwiazdy Kleene zmusza rozmiar zestawu do skończenia.

MathematicalOrchid

Zależy. Jakie inne podmioty są dozwolone? Jeśli dopuścisz komplementację, to, co mówisz, nie jest prawdą. Pytasz także o sytuację z gwiazdą Kleene, więc i tak musisz to wyjaśnić.

Raphael

Zobacz także cs.stackexchange.com/q/12624/755

Odpowiedzi:

Hendrik Jan daje dobrą odpowiedź na klasę złożoności, ale nie sam algorytm.

Najprostszym algorytmem, który to znam, jest konwersja wyrażenia regularnego na DFA. Znane są techniki konwertowania wyrażeń regularnych na NFA, a NFA na DFA.

Gdy masz dwa DFA, testowanie równoważności jest wydajne i rozstrzygalne, ponieważ minimalna postać DFA jest unikalna aż do izomorfizmu.

Jednak zbudowanie tych DFA z NFA może zająć dużo czasu i wytworzyć niezwykle duże DFAS, wykładniczo duże w najgorszym przypadku.

jmite
źródło

Wiadomo, że równoważność wyrażeń regularnych jest kompletna z PSPACE, co jest raczej złe. W artykule „Złożoność problemów decyzyjnych dla prostych wyrażeń regularnych” wymieniono kilka podklas wyrażeń regularnych wraz z ich złożonością. ( link )

Hendrik Jan
źródło

e^{2}

$e^2$

e e

$ee$

@dkuper Dziękujemy za dodatkowe wyjaśnienie. Edytuj odpowiedź, aby dodać tę lub odpowiednie odniesienia. (Lub nawet rozpocznij własną odpowiedź.)

Hendrik Jan

Czy istnieje odniesienie do ogólnych wyrażeń regularnych do uzupełnienia PSPACE?

Ryan

Twój link jest martwy. Czy możesz podać nową lub przynajmniej kilka istotnych informacji z gazety?

D. Ben Knoble,

@ D.BenKnoble Link działa dla mnie dobrze.

Hendrik Jan