Algorytm konwersji bardzo dużego NFA na DFA

12

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?

Jendas
źródło
wideo jest najwyraźniej na standardowym algorytmie determinującym. patrz np. minimalizacja NFA bez determinacji, stackoverflow
vzn 16.07.13
Jeśli wykonasz naiwną konwersję NFA-> DFA (używając konstrukcji produktu), jak duży jest wynikowy DFA? (przed minimalizacją)
DW
2
Co chcesz zrobić z DFA? Jeśli jesteś zainteresowany sprawdzaniem włączenia, istnieją algorytmy, aby to zrobić bezpośrednio.
Vijay D
Dziękuję za bardzo szybkie odpowiedzi. Jeśli chodzi o rozmiar, nie mogę dokładnie powiedzieć, ponieważ skończyła się moja pamięć RAM, ale dam mu dokładniejsze spojrzenie i rozszerzę pytanie. Jeśli chodzi o to, co chcę robić, nie jestem pewien, czy mogę otwarcie o tym rozmawiać, ponieważ jest to trochę moja fachowa wiedza. Ale z pewnością mogę stwierdzić, że tak naprawdę potrzebuję powstałego DFA.
Jendas,
1
Czy próbowałeś uruchomić algorytm Angluin do uczenia się DFA na podstawie zapytań dotyczących członkostwa i równoważności? Członkostwo jest łatwe (po prostu uruchom DFA na wymaganym łańcuchu); dla równoważności możesz narysować wiele losowych ciągów lub wypróbować wszystkie ciągi o określonej długości. To tylko heurystyka, ponieważ tak naprawdę nigdy nie dowiesz się, kiedy skończysz, ale odkryłem, że ta sztuczka działa dobrze w praktyce ...
Aryeh

Odpowiedzi:

6

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ł:

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 .

DW
źródło
Algorytm Brzozowskiego wydaje się obiecujący, ale technika dzielenia i podbijania jeszcze bardziej! W moim przypadku jest to naprawdę łatwe i nie wymaga dużych zmian kodu. Zrobię to i jeśli to zadziała, przyjmuję twoją odpowiedź.
Jendas,
2
Przybyłem, zapytałem, podzieliłem się, zwyciężyłem
Jendas
2

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:

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 :

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.

vzn
źródło
patrz także O
obniżkach