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

16

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.

Wesner Moise
źródło
Czy są jakieś ograniczenia dotyczące klasy NFA, które chciałbyś zaakceptować jako dane wejściowe? Niektóre ograniczenia prowadzą do lepszych górnych granic.
András Salamon,
nie jest to bardzo ważny punkt, ale czy ndfa musi być własnym tagiem?
Lew Reyzin
Tak, są ograniczenia. NFA są konstruowane bezpośrednio z wyrażeń regularnych, traktując je jako uogólnione wykresy przejściowe. seas.upenn.edu/~cit596/notes/dave/regexp-nfa4.html
Wesner Moise

Odpowiedzi:

15

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.

Aryabhata
źródło
pytanie dotyczy „algorytmu” działającego w podwykładniczym czasie i przestrzeni do konwersji NFA.
Marcos Villagra
@Marcos: Jeśli Twój wynik ma charakter wykładniczy, prawdopodobnie nie możesz mieć algorytmu działającego w czasie podwykładniczym.
Aryabhata,
1
To ogólny wynik. Jeśli znane są ograniczenia dotyczące klasy wejściowych NFA, może być lepiej.
András Salamon,
@Andras: Zgadzam się, ale biorąc pod uwagę, że jest to prawdopodobnie związane z programowaniem (które będzie obsługiwać Kleen * itp.), Wątpię, czy zestaw wejściowych NFA będzie ograniczony do odpowiedniego podzbioru.
Aryabhata,
5
Ten wynik został ostatnio wzmocniony przy użyciu trzyliterowego alfabetu, a konstrukcja jest nieco prostsza: portal.acm.org/…
13

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.

Noam
źródło
8

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).

Alexandre Passos
źródło
Czy można to przekształcić w argument, który mówi „jeśli w NFA uniknie się (czegoś złego), to DFA ma podwykładniczą liczbę stanów”?
András Salamon,
1
@ András, tak. „Jeśli w NFA unika się niedeterminizmu, wówczas DFA ma podwykładniczą liczbę stanów”.
P Shved
2
Pavel, tak, oczywiście. Czy istnieje jakakolwiek nietrywialna właściwość, którą można skutecznie rozpoznać, która gwarantuje również podwykładniczy wybuch?
András Salamon