Czy istnieją „małe” maszyny, które mogą skutecznie dopasowywać wyrażenia regularne?

Dobrze wiadomo, że wyrażenie regularne może zostać rozpoznane przez niedeterministyczny automat skończony o wielkości proporcjonalnej do wyrażenia regularnego lub przez deterministyczny FA, ​​który jest potencjalnie większy wykładniczo. Ponadto, biorąc pod uwagę ciąg i wyrażenie regularne , NFA może przetestować członkostwo w czasie proporcjonalnym do | s | \ cdot | r | , a DFA może przetestować członkostwo w czasie proporcjonalnym do | s | . Spowolnienie dla NFA wynika z faktu, że zasadniczo musimy śledzić zestawy możliwych stanów, w których może znajdować się automat, a wykładniczy wybuch dla DFA wynika z faktu, że jego stany są elementami zestawu sił stanów NFA.r | s | ⋅ | r | | s $s$$r$$|s| \cdot |r|$$|s|$

Czy jest możliwe efektywne (tj. Z czasem lepsze niż $O(|r| \cdot |s|)$ i lepsze miejsce niż $O(2^{|r|})$ ) rozpoznawanie wyrażeń regularnych, jeśli pozwolimy na użycie mocniejszych maszyn niż skończone automaty? (Na przykład, czy są zwięzłe korzyści w rozpoznawaniu zwykłych języków za pomocą automatów pushdown lub liczników?)

Łatwo jest wymienić czas na przestrzeń w następujący sposób.

Konwertuj wyrażenie regularne na NFA - dla konkretności przy porównywaniu algorytmów założymy, że jest liczbą stanów NFA, więc twój czas O ( r s ) związany z bezpośrednią symulacją NFA jest prawidłowy, a twój O ( 2 r ) przestrzeń związana z uruchomieniem przekonwertowanego DFA jest również ważna za każdym razem, gdy pracujesz w pamięci RAM, która może zająć tak dużo pamięci.$r$$O(rs)$$O(2^r)$

Teraz podzielić stany NFA (arbitralnie) do podzbiorów S I co najwyżej ⌈ r / k ⌉ Zjednoczonych każdego. W obrębie każdego podzbioru Ś I , można podzbiory indeks I z S ı liczbami od 0 do 2 ⌈ R / K ⌉ - 1 .$k$$S_i$$\lceil r/k\rceil$$S_i$$A_i$$S_i$$0$$2^{\lceil r/k\rceil}-1$

Zbuduj tabelę gdzie i oraz j mieszczą się w zakresie od 0 do k - 1 , c jest symbolem wejściowym, a A i jest (indeks numeryczny) podzbiorem S i . Wartości przechowywane w tabeli oznacza (wskaźnik liczbowy) podzbiór S j : stan Y jest T [ ı , j , c , A ı ] wtedy i tylko wtedy, gdy$T[i,j,c,A_i]$$i$$j$$k-1$$c$$A_i$$S_i$$S_j$$y$$T[i,j,c,A_i]$ należy do S j a jest to stan, w A, i który przechodzi do Y na symbol wejściowy C .$y$$S_j$$A_i$$y$$c$

Aby symulować NFA, utrzymania indeksy, po jednym dla każdego S I , określając podgrupie A ja z państw, w S í do których można dotrzeć za pośrednictwem prefiksu wejścia. Dla każdego symbolu wejściowego , c , za pomocą tabel sprawdzić dla każdej pary i , j , zestaw stanów w S j , który może być osiągnięty ze stanu w A ı przez przejście na C , a następnie użycie binarnego logicznym OR operacja na wskaźnikach liczbowych tych zestawów stanów, aby połączyć je w jeden podzbiór stanów S $k$$S_i$$A_i$$S_i$$c$$i,j$$S_j$$A_i$$c$$S_j$. Zatem każdy etap symulacji wymaga czasu , a całkowity czas symulacji wynosi O ( s k 2 ) .$O(k^2)$$O(sk^2)$

Wymagane miejsce to miejsce dla wszystkich tabel, którym jest . Analiza czasu i przestrzeni obowiązuje dla każdej pamięci RAM, która może zająć tak dużo pamięci i która może wykonywać operacje binarne na słowach, które są wystarczająco duże, aby zająć taką pamięć.$O(k^2 2^{r/k})$

Wynikający z tego kompromis czasoprzestrzenny nie pasuje idealnie do symulacji NFA, z powodu kwadratowej zależności od . Ale potem, jestem sceptyczny, że O ( r s ) jest właściwy czas związany do symulacji NFA: jak można symulować jeden krok NFA szybciej niż patrząc na wszystko z (wielu) kwadratowo ewentualnie przejść dozwolonych od aktualnie stan aktywny do innego stanu? Czy nie powinno to być O ( r 2 s ) ?$k$$O(rs)$$O(r^2 s)$

W każdym przypadku, pozwalając zmieniać, możesz uzyskać ograniczenia czasowe na kontinuum między granicami DFA i NFA, z mniejszą ilością miejsca niż DFA.$k$

To nie jest odpowiedź, ale za długa na komentarz. Próbuję wyjaśnić, dlaczego postawione pytanie może być trudne do zrozumienia.

Istnieją dwa sposoby definiowania złożoności obliczeniowej dla urządzenia o X .

Pierwszy i najbardziej naturalny sposób jest nieodłączny . Trzeba powiedzieć, w jaki sposób urządzenie X wykorzystuje dane wejściowe, abyśmy mogli później przyjrzeć się, jak rozmiar n danych wejściowych wpływa na czas działania urządzenia. Trzeba też powiedzieć, co liczy się jako operacja (lub krok ). Następnie po prostu pozwalamy, aby urządzenie działało na operacjach wprowadzania i zliczania.

$O(f(n))$$f(n)$

Na przykład wewnętrzna definicja NFA mówi, że przetworzenie ciągu o długości n wymaga n kroków ; zewnętrzna definicja, która używa maszyny RAM jako urządzenia Y, mówi, że najlepiej znana górna granica to prawdopodobnie odpowiedź Davida Eppsteina. (W przeciwnym razie byłoby dziwne, że (1) najlepsza praktyczna implementacja wskazana w drugiej odpowiedzi nie korzysta z lepszej alternatywy i (2) nikt tutaj nie wskazał lepszej alternatywy.) Zauważ też, że ściśle mówiąc, twoje urządzenie X jest wyrażeniem regularnym , ale ponieważ NFA ma ten sam rozmiar, można go bezpiecznie traktować jako urządzenie X , na które patrzysz.

$\Omega(f(n))$

W pewnym sensie najlepszą odpowiedzią, na jaką można mieć nadzieję, jest dowód w czymś takim jak model sondy komórkowej, że symulacja NFA wymaga pewnego czasu. (Pamiętaj, że jeśli weźmiesz pod uwagę konwersję NFA do DFA, potrzebujesz czasu na spisanie dużego DFA, więc pamięć nie jest jedynym problemem.)

Nawet jeśli uważasz, że nie ma nic nowego ani starego do nauczenia się w dopasowywaniu wyrażeń regularnych, sprawdź jeden z najpiękniejszych artykułów, na które natknąłem się od dawna: gra wyrażeń regularnych S Fischera, F Hucha i T Wilke, ICFP 2010.

(MMT Chakravarty zasługuje na uznanie za rekomendację tego artykułu).

EDYCJA: Powodem, dla którego ten artykuł jest istotny, jest to, że opisuje nową technikę (opartą na Glushkovie z lat 60.), która pozwala uniknąć budowy pełnego NFA (nie mówiąc już o DFA) odpowiadającego RE. To, co jest zrobione, przypomina uruchomienie algorytmu znakowania podobnego do znanego do decydowania o przyjęciu słowa przez NFA w drzewie składni RE. Pomiary wydajności sugerują, że jest to konkurencyjne, nawet w niedawno opublikowanej bibliotece Google re2.

Spójrz na ten artykuł Russ Cox. Opisuje podejście oparte na NFA, po raz pierwszy zastosowane przez Kena Thompsona, za pomocą którego ciąg wejściowy s można dopasować do wyrażenia regularnego rw czasie O (| s | .c ) i spacji O (| r |. D ), gdzie c i d są stałymi górnymi. Artykuł szczegółowo opisuje implementację techniki w języku C.