Jakie algorytmy istnieją do budowy DFA, który rozpoznaje język opisany przez dane wyrażenie regularne?

Wszystkie moje podręczniki używają tego samego algorytmu do tworzenia DFA, biorąc pod uwagę regex: Najpierw utwórz NFA, który rozpoznaje język regex, a następnie, używając konstrukcji podzbioru (aka „powerset”), przekonwertuj NFA na równoważny DFA ( opcjonalnie minimalizując DFA). Kiedyś słyszałem też, jak profesor wspomina o istnieniu innych algorytmów. Czy ktoś o tym wie? Być może taki, który przechodzi bezpośrednio z wyrażenia regularnego do DFA bez pośredniego NFA?

Istnieją różne algorytmy do konwersji wyrażeń regularnych na automaty skończone. Możesz przejść bezpośrednio z wyrażeń regularnych do DFA bez wcześniejszego budowania innego automatu, domyślnie wykonując konstrukcję podzbioru podczas generowania automatu. Inną opcją bezpośredniego uzyskania deterministycznych automatów jest zastosowanie metody pochodnych.

Sprawdzenie, czy wyrażenie regularne reprezentuje język zawierający wszystkie ciągi, jest problemem kompletnym PSPACE (zobacz tę odpowiedź w celach informacyjnych). Sprawdzanie, czy DFA akceptuje ten język, można wykonać w czasie wielomianowym, więc jeśli przejdziesz bezpośrednio z wyrażenia regularnego do DFA, nastąpi gdzieś wysadzenie.

Rozumiem literaturę, że możemy wybrać tłumaczenia, które pozwolą nam zlokalizować powiększenie. Oznacza to, że istnieją różne sposoby przejścia od wyrażenia regularnego do skończonego automatu i preferowane są metody liniowe lub wielomianowe. Zazwyczaj koszty wykładnicze są spychane w celu ustalenia automatów.

Dużo pracy włożono w identyfikację podrodzin wyrażeń regularnych, z których możemy skutecznie generować DFA. Ta linia pracy zależy od używanego tłumaczenia. Oznacza to, że naprawiasz mapowanie wyrażeń regularnych na NFA i próbujesz scharakteryzować wyrażenia regularne, które są mapowane na DFA.

Standardowa konstrukcja automatów z wyrażeń regularnych nie jest preferowaną konstrukcją w takich pracach. Wybrane konstrukcje produkują automaty, które ściśle przypominają strukturę wyrażenia regularnego. Konstrukcje te używają pojęcia pochodnej wyrażenia regularnego.

Pochodne wyrażeń regularnych , JA Brzozowski. 1964 r.

Pochodna $s$ wyrażenia regularnego $r$ w odniesieniu do symbolu $a$ z alfabetu to wyrażenie regularne reprezentujące język $r$ z wiodącym $a$usunięte z ciągów. Pojęcie to zostało rozszerzone przez Antimirowa na częściowe pochodne wyrażeń regularnych.

Częściowe pochodne wyrażeń regularnych i konstrukcji automatów skończonych , V. Antimirov. 1995.

Jeśli myślisz o stanie automatu jako reprezentacji wszystkich ciągów znaków przyjętych z tego stanu, pochodne (częściowe) pozwalają traktować wyrażenia regularne jak stany . Porównaj ze standardową konstrukcją podręcznika, która intuicyjnie traktuje wyrażenia regularne jako automaty, a nie stany.

Od wyrażeń regularnych po deterministyczne automaty , G. Berry i R. Sethi, 1986.

Zgodność między wyrażeniami regularnymi i stanami automatu a determinizmem jest wyraźnie omawiana przez Berry'ego i Sethiego, którzy łączą pojęcie pochodnych Brzozowskiego z ideą rozróżnienia między wystąpieniami tego samego symbolu, aby uzyskać oparte na składni tłumaczenie tłumaczenia wyrażeń regularnych na skończone automaty.

Jeden jednoznaczny język regularny , A. Brüggemann-Klein i Derick Wood, 1998.

Ten artykuł opiera się na wcześniejszych pracach Brüggemann-Klein i analizuje przypadki, w których można wykorzystywać pochodne do generowania DFA w czasie wielomianowym. Po tym dokumencie jest dużo pracy. Było to istotne z punktu widzenia technologii sieciowych, ponieważ wyrażenia regularne, którymi można skutecznie manipulować (czyli odpowiadające DFA), były ważne dla przetwarzania SGML i XML.

Dużo pracy poświęcono badaniu innych specjalnych przypadków deterministycznych wyrażeń regularnych. Bardzo niedawny artykuł badający, kiedy niektóre z tych problemów można rozwiązać w czasie liniowym, pochodzi z 2012 roku.

Deterministyczne wyrażenia regularne w czasie liniowym , Benoit Groz, Sebastian Maneth, Sławomir Staworko. 2012.