Algorytm konwersji bardzo dużego NFA na DFA

Mam naprawdę duży niedeterministyczny automat skończony i muszę go przekonwertować na DFA.

Przez duże rozumiem ponad 40 000 stanów. Do tej pory przeprowadziłem kilka eksperymentów i zaprogramowałem domyślny algorytm, który przeszukuje tabelę (jak opisano tutaj ), ale nawet po optymalizacji jest dość powolny i bardzo zajmuje pamięć. Zdaję sobie sprawę z tego, że liczba stanów może rosnąć wykładniczo, ale po zminimalizowaniu wynikowy DFA ma około 9 000 stanów i jest to możliwe.

Moje pytanie brzmi: czy istnieje jakiś algorytm, który byłby szybszy lub bardziej przyjazny dla pamięci?

Czy próbowałeś algorytmu Brzozowskiego ? W najgorszym przypadku czas działania jest wykładniczy, ale widzę pewne referencje sugerujące, że często działa bardzo dobrze, szczególnie gdy zaczynasz od NFA, który chcesz przekonwertować na DFA i zminimalizować.

Wydaje się, że następujący artykuł:

• O wydajności algorytmów minimalizacji automatów , Marco Almeida, Nelma Moreira, Rogerio Reis.

Ocenia szereg różnych algorytmów minimalizacji DFA, w tym ich zastosowanie do sytuacji, w której zaczynamy od NFA i chcemy przekonwertować go na DFA i zminimalizować.

Jak wygląda rozkład silnie połączonych komponentów (SCC) twojego NFA (biorąc pod uwagę, że jest to wykres kierowany)? Czy ma wiele elementów, z których żaden nie jest zbyt duży? Jeśli tak, zastanawiam się, czy można opracować algorytm dzielenia i zdobywania, w którym bierzesz pojedynczy komponent, konwertujesz go z NFA na DFA, a następnie minimalizujesz, a następnie zastępujesz oryginał nową, określoną wersją. Powinno to być możliwe w przypadku komponentów z jednym wejściem (gdy wszystkie krawędzie tego komponentu prowadzą do pojedynczego wierzchołka, wierzchołka wejściowego). Nie od razu widzę, czy byłoby możliwe zrobienie czegoś takiego dla arbitralnych NFA, ale jeśli sprawdzisz, jak wygląda struktura SCC, możesz być w stanie ustalić, czy ten kierunek warto zbadać, czy nie .

najwyraźniej nie jest to dobrze zbadany problem w sensie znanych / dostępnych algorytmów innych niż pierwotna / dawna strategia „określania na DFA / minimalizowania DFA”. wydaje się, że wskazujesz, że etap determinacji jest problematyczny, ale jest to typowe, oczywiście biorąc pod uwagę, że ma on gorszy przypadek wykładniczo-przestrzenno-czasowy. należy pamiętać, że istnieje kilka algorytmów minimalizacji DFA, które mogą znacznie różnić się wydajnością średnio.

jest również znany bardziej nieformalnie jako „minimalizacja NFA bez determinacji” . wiadomo, że jest trudne w tym sensie, że w zasadzie nie ma nawet algorytmów aproksymacyjnych, chyba że P = Pspace, jak pokazano w tym artykule:

• Minimalizowanie NFA i wyrażeń regularnych Gregor Gramlich, Georg Schnitger

Jednak dokument ten uważa się na ogół rzadko zbadane przypadku niektórych algorytmów, które nie są oparte na znalezienie determinized DFA 1 ^st :

• Algorytmy redukcji NFA za pomocą regularnych nierówności Jean-Marc Champarnaud, Fabien Coulon

Prezentujemy różne techniki zmniejszania liczby stanów i przejść w niedeterministycznych automatach. Techniki te opierają się na dwóch zamówieniach w zestawie stanów związanych z włączeniem lewego i prawego języka. Ponieważ ich dokładne obliczenia są trudne dla NP, skupiamy się na aproksymacjach wielomianowych, które umożliwiają jednakowe zmniejszenie NFA.

zwróć uwagę na publicznie dostępny pakiet / implementację, który może obsługiwać duże konwersje / minimalizacje NFA / DFA itp., na ogół tak skutecznie, jak to możliwe, to biblioteka AT&T FSM .

ma strategię, fsmcompactktóra czasem może wystarczyć:

W przypadkach, gdy przetwornik lub ważony akceptor nie mogą być określone lub stają się bardzo duże, przydatna może być inna optymalizacja fsmcompact. Ta operacja koduje każdą potrójną etykietę wejściową, etykietę wyjściową i koszt w pojedynczej nowej etykiecie, wykonuje klasyczne (nieważone akceptor) określenie i minimalizację, a następnie dekoduje zakodowane etykiety z powrotem do ich oryginalnych wartości. Ma to tę zaletę, że jest zawsze zdefiniowane i nie przesuwa etykiet wyjściowych ani kosztów wzdłuż ścieżek. Ma tę wadę, że wynik nie może być ani deterministyczny, ani minimalny.