Czy niedeterministyczne skończone automaty (NDFA) można skutecznie konwertować na deterministyczne skończone automaty (DFA) w podwykładniczej przestrzeni / czasie?

Dwadzieścia lat temu zbudowałem pakiet wyrażeń regularnych, który obejmował konwersje wyrażeń regularnych na maszynę skończoną (DFA) i obsługiwał wiele zamkniętych operacji wyrażeń regularnych (gwiazda Kleene, konkatenacja, operacje odwrotne, ustawianie itp.). Nie byłem pewien co do najgorszej wydajności mojego pakietu.

DFA ma taką samą moc ekspresyjną jak NDFA, ponieważ NDFA w stanie n można w trywialny sposób przekształcić w DFA o 2 ^ n stanach. Czy istnieją jednak dolne górne granice gwarancji dla takiej konwersji, które nie wymagają wykładniczej eksplozji w stanie?

Nie byłem w stanie wymyślić przykładów źle zachowujących się wyrażeń regularnych lub NDFA, ale nie zastanawiałem się długo. Zgaduję wyrażenie regularne, takie jak (((((e | A | B | C)) * (e | D | E | F)) * (e | G | H | I)) * (e | J | K | L | M)) *, który miesza wiele naprzemienności, a gwiazdy Kleene miałyby liniowy rozmiar NDFA, ale ekspansywny DFA.

Wiadomo, że dla każdej pary liczb naturalnych n,atakich n <= a <= 2^n, że istnieje minimalna NDFA ze nstanami, których odpowiadający równoważny minimalny dfa ma astany (ponad czteroliterowy alfabet).

Zobacz artykuł tutaj: Deterministyczne powiększenia minimalnych niedeterministycznych automatów skończonych nad ustalonym alfabetem .

Streszczenie pracy:

Pokazujemy, że dla wszystkich liczb całkowitych n i α takich, że n ≤ α ≤ 2 ^ n, istnieje minimalny niedeterministyczny automat skończony n stanów z czteroliterowym alfabetem wejściowym, którego równoważny minimalny deterministyczny automat skończony ma dokładnie stany. Wynika z tego, że w przypadku czteroliterowego alfabetu nie ma „magicznych liczb”, tj. Dziur w hierarchii. Poprawia to podobny wynik uzyskany przez Gefferta dla rosnącego alfabetu o rozmiarze n + 2 (Proc. 7 DCFS, Como, Włochy, 23-37).

Tak więc przypuszczam, że odpowiedź na twoje pytanie brzmi: nie.

Klasycznym przykładem języka z wykładniczą separacją między rozmiarem DFA i rozmiarem NFA jest następujący język skończony: ciągi binarne o długości dokładnie 2n, w których pierwsza połowa nie jest równa drugiej połowie. NFA zgadnie indeks i, w którym pierwsza i druga połowa się nie zgadzają. Dolna granica dla DFA wynika na przykład ze złożoności komunikacji.

Minimalne DFA odpowiadające NFA ma w najgorszym przypadku 2 ^ stany, więc nie można niczego zagwarantować. Bez konstruktywnego przykładu, rozumowanie jest takie, że w NFA możesz znajdować się w dowolnym dowolnym podzbiorze stanów po przeczytaniu określonego ciągu wejściowego, a każdy taki podzbiór może zachowywać się inaczej, obserwując jeden znak. Załóżmy, że język składa się z dwóch znaków w alfabecie (a i b) oraz NFA N ze stanami n, które zaczynają się od stanu akceptacji na s_0. Teraz zliczyć wszystkie podzbiory stanów N i zbudować tabelę przejściową, tak że obserwowanie „a” z podzbioru S_i zabierze cię do podzbioru S_i + 1, a obserwacja b zabierze cię do podzbioru S_i-1 (myślę, że jest to wykonalne w przypadku niektórych wyliczeń ). Teraz automaty te mają n stanów i akceptują sekwencje ma i nb takie, że mn = 0 mod 2 ^ | N |, i nie można go wyrazić za pomocą DFA, który ma mniej niż 2 ^ | N | stany (ponieważ może być konieczne przechodzenie przez wszystkie podzbiory stanów NFA N).