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

11

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?

BlueBomber
źródło
Witamy w cstheory, witrynie pytań i odpowiedzi na pytania na poziomie badawczym w teoretycznej informatyce (TCS). Twoje pytanie nie wydaje się być pytaniem na poziomie badawczym w TCS. Zapoznaj się z często zadawanymi pytaniami, aby uzyskać więcej informacji o tym, co to oznacza. Twoje pytanie może być odpowiednie dla informatyki, która ma szerszy zakres.
Kaveh
1
dlaczego zawsze używasz tego komentarza do szablonu? Najwyraźniej jest co najmniej 5 osób, które się z tobą nie zgadzają. Proponuję dać szansę takim pytaniom.
AJed
@AJed, nie zawsze używam tego komentarza. Używam go, gdy pytanie wydaje mi się nie na temat, ale może być odpowiednie dla informatyki . Zwiększenie liczby głosów nie oznacza, że ​​pytanie dotyczy tematu, a to nie wydaje mi się pytaniem na poziomie badawczym, więc uważam, że komentarz jest odpowiedni. (Fakt, że ktoś może napisać odpowiedź na pytanie badawcze, nie czyni pytania pytaniem na poziomie badawczym.) Ps: Myślę, że ta dyskusja jest bardziej odpowiednia dla Meta Teoretycznej Informatyki .
Kaveh

Odpowiedzi:

13

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 za z alfabetu to wyrażenie regularne reprezentujące język r z wiodącym zausunię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.

Vijay D.
źródło
5
Wspomniałeś już o pochodnych w swojej odpowiedzi, więc powinieneś również dodać JA Brzozowski: Pochodne wyrażeń regularnych, Journal of the ACM 11 (4): 481–494 (1964), ponieważ podaje on bezpośredni algorytm konwersji wyrażeń regularnych na DFA .
Neel Krishnaswami
3
Dyskutowałem o tym. Ale wszystkie trzy powyższe artykuły bezpośrednio opierają się na tym wyniku, więc pomyślałem, że nie ma powodu o tym wspominać. Papier Brueggeman-Klein i Wood jest również pełen przykładów. Jeśli wspomnę o Brzozowskim, uważam, że Antimirov również powinien zostać wymieniony. Chciałem uniknąć ankiety, ale może powinienem po prostu ją wziąć. Co powiedzieć?
Vijay D
5
Jeśli masz czas i energię, myślę, że długie odpowiedzi podobne do badań są tutaj bardzo odpowiednie.
David Eppstein
1
@VijayD: tak, zgadzam się z Davidem. Krótkie odpowiedzi są w porządku, ale jeśli masz energię, miło jest udzielić wyczerpującej odpowiedzi.
Neel Krishnaswami