Jak przekonwertować automaty skończone na wyrażenia regularne?
On 16 lutego, 2021 by adminKonwersja wyrażeń regularnych na (minimalne) NFA akceptujące ten sam język jest łatwa dzięki standardowym algorytmom, np. Algorytm Thompsona . Drugi kierunek wydaje się jednak bardziej żmudny i czasami wynikowe wyrażenia są nieczytelne.
Jakie algorytmy są tam do konwersji NFA na równoważne wyrażenia regularne? Czy są jakieś zalety związane ze złożonością czasową lub rozmiarem wyniku?
To ma być pytanie referencyjne. Proszę dołączyć ogólny opis metody, a także nietrywialny przykład.
Komentarze
- Zwróć uwagę na podobne pytanie na cstheory.SE , który prawdopodobnie nie jest odpowiedni dla naszych odbiorców.
- wszystkie odpowiedzi używają formalnej techniki pisania RE z DFA. Uważam, że moja technika przez analizę jest stosunkowo łatwa i obiektywna, którą demonstruję w mojej odpowiedzi : Jaki jest język tych deterministycznych automatów skończonych? Wydaje mi się, że kiedyś by się to przydało. Tak, oczywiście czasami sam używam metody formalnej (twierdzenie Ardena) napisać RE jest pytanie jest złożone, jak podano w tym przykładzie: Jak napisać wyrażenie regularne dla DFA
Odpowiedź
Istnieje kilka metod konwersji z automatów skończonych na wyrażenia regularne. Tutaj opiszę tę, której zwykle uczy się w szkole, która jest bardzo wizualna. Uważam, że jest najczęściej używany w praktyce. Jednak napisanie algorytmu nie jest dobrym pomysłem.
Metoda usuwania stanu
Ten algorytm dotyczy obsługi wykresu automatu i dlatego nie jest zbyt odpowiedni dla algorytmów, ponieważ wymaga prymitywy grafów, takie jak … usuwanie stanów. Opiszę to za pomocą prymitywów wyższego poziomu.
Kluczowa idea
Pomysł polega na rozważeniu wyrażeń regularnych na krawędziach, a następnie usunięciu stanów pośrednich przy zachowaniu spójności etykiet krawędzi.
Główny wzorzec można zobaczyć na poniższych rysunkach. Pierwsza ma etykiety między $ p, q, r $, które są wyrażeniami regularnymi $ e, f, g, h, i $ i chcemy usunąć $ q $.
Po usunięciu składamy razem $ e, f, g, h, i $ (zachowując pozostałe krawędzie między $ p $ a $ r $, ale nie jest to wyświetlane na tym):
Przykład
Korzystając z tego samego przykładu co w Odpowiedź Rafaela :
sukcesywnie usuwamy $ q_2 $:
a następnie $ q_3 $:
to nadal musimy zastosować gwiazdkę do wyrażenia od $ q_1 $ do $ q_1 $. W tym przypadku stan końcowy to również początkowa, więc naprawdę musimy dodać gwiazdkę:
$$ (ab + (b + aa) (ba) ^ * (a + bb)) ^ * $$
Algorytm
L[i,j]
to wyrażenie regularne języka od $ q_i $ do $ q_j $. Najpierw usuwamy wszystkie mul ti-edge:
for i = 1 to n: for j = 1 to n: if i == j then: L[i,j] := ε else: L[i,j] := ∅ for a in Σ: if trans(i, a, j): L[i,j] := L[i,j] + a
A teraz usunięcie stanu. Załóżmy, że chcemy usunąć stan $ q_k $:
remove(k): for i = 1 to n: for j = 1 to n: L[i,i] += L[i,k] . star(L[k,k]) . L[k,i] L[j,j] += L[j,k] . star(L[k,k]) . L[k,j] L[i,j] += L[i,k] . star(L[k,k]) . L[k,j] L[j,i] += L[j,k] . star(L[k,k]) . L[k,i]
Zauważ, że zarówno ołówkiem papierowym, jak i algorytmem powinieneś uprościć wyrażenia takie jak star(ε)=ε
, e.ε=e
, ∅+e=e
, ∅.e=∅
(przez ręką po prostu nie piszesz krawędzi, gdy nie jest to $ ∅ $, a nawet $ ε $ dla pętli własnej i ignorujesz, gdy nie ma przejścia między $ q_i $ a $ q_k $ lub $ q_j $ i $ q_k $)
A teraz, jak używać remove(k)
? Nie powinieneś lekko usuwać stanów końcowych lub początkowych, w przeciwnym razie stracisz część języka.
for i = 1 to n: if not(final(i)) and not(initial(i)): remove(i)
Jeśli masz tylko jeden stan końcowy $ q_f $ i jeden stan początkowy $ q_s $ to końcowe wyrażenie to:
e := star(L[s,s]) . L[s,f] . star(L[f,s] . star(L[s,s]) . L[s,f] + L[f,f])
Jeśli masz kilka stanów końcowych (lub nawet stanów początkowych), nie ma prostego sposobu na połączenie te, inne niż zastosowanie metody domknięcia przechodniego. Zwykle nie jest to problem ręczny, ale jest to niewygodne podczas pisania algorytmu. O wiele prostszym obejściem jest wyliczenie wszystkich par $ (s, f) $ i uruchomienie algorytmu na (już usuniętym stanie) wykresie, aby uzyskać wszystkie wyrażenia $ e_ {s, f} $ zakładając, że $ s $ jest jedynym stanem początkowym a $ f $ jest jedynym stanem końcowym, a następnie sumowanie wszystkich $ e_ {s, f} $.
To oraz fakt, że modyfikuje to języki bardziej dynamicznie niż pierwsza metoda sprawia, że bardziej podatne na błędy podczas programowania. Proponuję użyć dowolnej innej metody.
Wady
W tym algorytmie jest wiele przypadków, na przykład przy wyborze węzła do usunięcia, liczbie stanów końcowych na końcu , fakt, że stan końcowy może być również początkowy itp.
Zauważ, że teraz, gdy algorytm jest napisany, jest to bardzo podobne do metody domknięcia przechodniego.Tylko kontekst użycia jest inny. Nie polecam implementacji algorytmu, ale użycie metody ręcznej jest dobrym pomysłem.
Komentarze
- W przykładzie, drugi obraz, po usunięciu węzła ” 2 „, brak krawędzi – krawędź pętli (ab) w węźle A.
- @Kabamaru: Naprawiono. Ale teraz myślę, że $ \ varepsilon $ na trzecim obrazku również powinno być
ab
, i podobnie być może w końcowym wyrażeniu regularnym. - Możesz ustawić algorytm pracować dla dowolnej liczby stanów początkowych i końcowych, dodając nowy stan początkowy $ q ^ + $ i nowy stan końcowy $ q ^ – $ i łącząc je ze stanami początkowymi i końcowymi za pomocą $ \ varepsilon $ -edges. Teraz usuń wszystkie pierwotne stany. Wyrażenie znajduje się następnie na pojedynczej pozostałej krawędzi od $ q ^ + $ do $ q _- $. Konstrukcja nie da pętli na $ q ^ + $ lub $ q _- $, ponieważ te stany nie mają wchodzących odpowiednio. wychodzące krawędzie. Lub jeśli jesteś ścisły, będą miały etykiety reprezentujące pusty zestaw.
- Nadal jest problem z drugim przykładem: przed uproszczeniem automat akceptuje ” ba „, (1, 3, 1) ale po uproszczeniu nie ' t.
Odpowiedź
Metoda
Najładniejsza metoda, jaką widziałem, to taka, która wyraża automat jako system równań (regularnych) języków, być rozwiązane. Jest to szczególnie przyjemne, ponieważ wydaje się dawać bardziej zwięzłe wyrażenia niż inne metody.
Niech $ A = (Q, \ Sigma, \ delta, q_0, F) $ an NFA bez $ \ varepsilon $ – przejścia. Dla każdego stanu $ q_i $ utwórz równanie
$ \ qquad \ displaystyle Q_i = \ bigcup \ limit_ {q_i \ overset {a} {\ to} q_j} aQ_j \ cup \ zacząć {przypadków} \ {\ varepsilon \} &, \ q_i \ in F \\ \ emptyset &, \ text {else} \ end {cases} $
gdzie $ F $ jest zbiorem stanów końcowych, a $ q_i \ overset {a} {\ to} q_j $ oznacza przejście od $ q_i $ do $ q_j $ oznaczone jako $ a $ . Jeśli przeczytasz $ \ cup $ jako $ + $ lub $ \ mid $ (w zależności od definicji wyrażenia regularnego), zobaczysz, że jest to równanie wyrażeń regularnych.
Do rozwiązania systemu potrzebujesz asocjatywności i dystrybutywność $ \ cup $ i $ \ cdot $ (konkatenacja ciągów), przemienność $ \ cup $ i lematu Ardena ¹:
Niech $ L, U, V \ subseteq \ Sigma ^ * $ regularne języki z $ \ varepsilon \ notin U $. Następnie
$ \ qquad \ displaystyle L = UL \ cup V \ quad \ Longleftrightarrow \ quad L = U ^ * V $
Rozwiązaniem jest zbiór wyrażeń regularnych $ Q_i $, po jednym dla każdego stanu $ q_i $. $ Q_i $ opisuje dokładnie te słowa, które mogą być akceptowane przez $ A $ rozpoczynając w $ q_i $; dlatego $ Q_0 $ (jeśli $ q_0 $ jest stanem początkowym) jest żądane wyrażenie.
Przykład
Dla jasności oznaczymy pojedyncze zestawy za pomocą ich elementu, tj. $ a = \ {a \} $. Przykład należy do Georga Zetzschego.
Rozważmy t jego NFA:
[ źródło ]
Odpowiedni układ równań to:
$ \ qquad \ begin {align} Q_0 & = aQ_1 \ cup bQ_2 \ cup \ varepsilon \\ Q_1 & = bQ_0 \ cup aQ_2 \\ Q_2 & = aQ_0 \ cup bQ_1 \ end {align} $
Teraz podłącz trzecie równanie do drugiego:
$ \ qquad \ begin {align} Q_1 & = bQ_0 \ cup a (aQ_0 \ cup bQ_1) \\ & = abQ_1 \ cup (b \ cup aa) Q_0 \\ & = (ab) ^ * ( b \ cup aa) Q_0 \ end {align} $
W ostatnim kroku zastosujemy lemat Ardena z $ L = Q_1 $, $ U = ab $ i $ V = (b \ cup aa) \ cdot Q_0 $. Zwróć uwagę, że wszystkie trzy języki są zwykłe i $ \ varepsilon \ notin U = \ {ab \} $, co pozwala nam zastosować lemat. Teraz dołączamy ten wynik do pierwszego równania:
$ \ qquad \ begin {align} Q_0 & = a (ab) ^ * (b \ cup aa ) Q_0 \ cup baQ_0 \ cup bb (ab) ^ * (b \ cup aa) Q_0 \ cup \ varepsilon \\ & = ((a \ cup bb) (ab) ^ * (b \ cup aa) \ cup ba) Q_0 \ cup \ varepsilon \\ & = ((a \ cup bb) (ab) ^ * (b \ cup aa) \ cup ba) ^ * \ qquad \ text {(według lematu Ardena)} \ end {align} $
W ten sposób znaleźliśmy wyrażenie regularne dla języka akceptowanego przez powyższy automat, a mianowicie
$ \ qquad \ displaystyle ((a + bb) (ab) ^ * (b + aa) + ba) ^ *. $
Zauważ, że jest dość zwięzły (porównaj z wynik innych metod), ale nie jest to jednoznacznie określone; rozwiązanie układu równań z inną sekwencją manipulacji prowadzi do innych – równoważnych! – wyrażeń.
- Aby udowodnić Arden ” lematu, patrz tutaj .
Komentarze
- Co jest złożoność czasowa tego algorytmu? Czy istnieje ograniczenie rozmiaru wyświetlanego wyrażenia?
- @jmite: Nie mam pojęcia. Nie ' nie sądzę, że ' nie próbuję tego wdrożyć (inne metody wydają się być bardziej wykonalne w tym zakresie), ale używam tego metoda papierowa.
- Tutaj ' z implementacją tego algorytmu w Prologu: github.com / wvxvw / intro-to-automata-teoria / blob / master / automata / … , ale jego predykat
maybe_union/2
może używać więcej pracy (szczególnie wrt eliminując wspólny prefiks), aby uporządkować wyrażenia regularne. Innym sposobem postrzegania tej metody jest rozumienie jej jako tłumaczenia wyrażenia regularnego na gramatykę liniowo-prawą, gdzie języki z ujednoliceniem podobnym do Prologu lub dopasowywaniem wzorców w stylu ML stanowią bardzo dobre przetworniki, więc ' to nie tylko algorytm pióra i papieru 🙂 - Tylko jedno pytanie. Ε w pierwszym równaniu wynika z tego, że Qo jest stanem początkowym, czy też ' jest stanem końcowym? Tak samo, jeśli mam dwa końcowe stany?
- @PAOK Sprawdź definicję $ Q_i $ powyżej (linia); to ' s, ponieważ $ q_0 $ jest stanem końcowym.
Odpowiedź
Metoda algebraiczna Brzozowskiego
Jest to ta sama metoda, co opisana w odpowiedzi Rafaela , ale z punktu spojrzenie na systematyczny algorytm, a następnie, w istocie, algorytm. Okazuje się, że jest łatwy i naturalny do wdrożenia, gdy wiesz, od czego zacząć. Może też być łatwiejsze ręcznie, jeśli narysowanie wszystkich automatów jest z jakiegoś powodu niepraktyczne.
Pisząc algorytm, musisz pamiętać, że równania muszą być zawsze liniowe, aby mieć dobrą abstrakcyjną reprezentację równań, o czym możesz zapomnieć, rozwiązując ręcznie.
Idea algorytmu
Nie będę opisywał, jak to działa, ponieważ jest dobrze zrobione w odpowiedzi Rafaela , co ja proponuję przeczytać wcześniej. Zamiast tego skupiam się na kolejności rozwiązywania równań bez wykonywania zbyt wielu dodatkowych czynności mputacje lub dodatkowe przypadki.
Zaczynając od reguły Ardena „pomysłowego rozwiązania $ X = A ^ * B $ do równania językowego $ X = AX∪B $ możemy traktować automat jako zbiór równań postaci:
$$ X_i = B_i + A_ {i, 1} X_1 +… + A_ {i, n} X_n $$
możemy rozwiązać ten problem przez indukcję na $ n $, odpowiednio aktualizując tablice $ A_ {i, j} $ i $ B_ {i, j} $. W kroku $ n $ mamy:
$$ X_n = B_n + A_ {n, 1} X_1 +… + A_ {n, n} X_n $$
i Reguła Ardena daje nam:
$$ X_n = A_ {n, n} ^ * (B_n + A_ {n, 1} X_1 +… + A_ {n, n-1} X_ {n -1}) $$
i ustawiając $ B „_n = A_ {n, n} ^ * B_n $ and $ A” _ {n, i} = A_ {n, n} ^ * A_ {n, i} $ otrzymujemy:
$$ X_n = B „_n + A” _ {n, 1} X_1 +… + A „_ {n, n-1} X_ {n -1} $$
i możemy wtedy usunąć wszystkie potrzeby $ X_n $ w systemie, ustawiając dla $ i, j < n $:
$$ B „_i = B_i + A_ {i, n} B” _n $$ A „_ {i, j} = A_ {i, j} + A_ {i, n} A „_ {n, j} $$
Kiedy rozwiążemy $ X_n $, gdy $ n = 1 $, otrzymamy takie równanie:
$$ X_1 = B” _1 $$
bez $ A „_ {1, i} $. W ten sposób otrzymaliśmy nasze wyrażenie regularne.
Algorytm
Dzięki temu możemy zbudować algorytm. Aby mieć taką samą konwencję jak w powyższej indukcji, powiemy, że stan początkowy to $ q_1 $, a liczba stanów to $ m $. Najpierw inicjalizacja w celu wypełnienia $ B $:
for i = 1 to m: if final(i): B[i] := ε else: B[i] := ∅
i $ A $:
for i = 1 to m: for j = 1 to m: for a in Σ: if trans(i, a, j): A[i,j] := a else: A[i,j] := ∅
a następnie rozwiązanie:
for n = m decreasing to 1: B[n] := star(A[n,n]) . B[n] for j = 1 to n: A[n,j] := star(A[n,n]) . A[n,j]; for i = 1 to n: B[i] += A[i,n] . B[n] for j = 1 to n: A[i,j] += A[i,n] . A[n,j]
końcowe wyrażenie to:
e := B[1]
Implementacja
Nawet jeśli wydaje się, że układ równań wydaje się zbyt symboliczny dla algorytmu, ten jest dobrze dostosowany do implementacji. Oto implementacja tego algorytmu w Ocaml (uszkodzony link) . Zwróć uwagę, że poza funkcją brzozowski
, wszystko jest do wydrukowania lub użycia dla przykładu Rafaela. Zauważ, że istnieje zaskakująco wydajna funkcja upraszczania wyrażeń regularnych simple_re
.
Komentarze
- Link nie działa …
- Implementacja w JavaScript: github.com/devongovett/regexgen/blob/master/src/regex.js
- Dziękuję za to wspaniałe wyjaśnienie. Jeśli dobrze rozumiem, Twój pseudokod inicjalizacyjny zakłada, że dla danego i i j istnieje co najwyżej jedno a takie, że (i, a, j) jest przejściem. Jest to poprawne, jeśli zgodzimy się oznaczyć to przejście wyrażeniem regularnym, które pasuje do wszystkich liter w Σ ta etykieta przechodzi z i do j w automacie z literami, ale wtedy twoja notacja a in Σ jest trochę dziwna, ponieważ tak naprawdę nie jest to litera. Jeśli pójdziemy litera po literze, możemy mieć kilka przejść z i do j i musimy wykonaj połączenie swoich etykiet w treści pętli.
Odpowiedź
Metoda domknięcia przechodniego
Ta metoda jest łatwa do napisania w formularzu algorytmu, ale generuje absurdalnie duże wyrażenia regularne i jest niepraktyczne, jeśli robisz to ręcznie, głównie dlatego, że jest to zbyt systematyczne. Jest to jednak dobre i proste rozwiązanie dla algorytmu.
Podstawowa idea
Niech $ R ^ k_ {i, j} $ reprezentuje wyrażenie regularne dla ciągów zaczynających się od $ q_i $ do $ q_j $ przy użyciu stanów $ \ {q_1,…, q_k \} $. Niech $ n $ będzie liczbą stanów automatu.
Załóżmy, że znasz już wyrażenie regularne $ R_ {i, j} $ od $ q_i $ do $ q_j $ bez stanu pośredniego $ q_k $ (z wyjątkiem kończyn), dla wszystkich $ i, j $. Następnie możesz zgadnąć, jak dodanie kolejnego stanu wpłynie na nowe wyrażenie regularne $ R „_ {i, j} $: zmienia się tylko wtedy, gdy masz bezpośrednie przejścia do $ q_k $ i można to wyrazić w ten sposób:
$$ R „_ {i, j} = R_ {i, j} + R_ {i, k}. R_ {k, k} ^ *. R_ {k, j} $$
($ R $ to $ R ^ {k-1} $ a $ R „$ to $ R ^ k $.)
Przykład
Skorzystamy z tego samego przykładu, co w odpowiedzi Raphaela . Na początku możesz używać tylko bezpośrednich przejść.
Oto pierwszy krok (zwróć uwagę, że pętla własna z etykietą $ a $ przekształciłaby pierwsze $ ε $ w $ (ε + a) $.
$$ R ^ 0 = \ begin {bmatrix} ε & a & b \\ b & ε & a \\ a & b & ε \ end {bmatrix} $$
W drugim kroku możemy użyć $ q_0 $ (która jest dla nas zmieniona na $ q_1 $, ponieważ $ R ^ 0 $ jest już używane do powyższy cel). Zobaczymy, jak działa $ R ^ 1 $.
Od $ q_2 $ do $ q_2 $: $ R ^ 1_ {2,2} = R ^ 0_ {2,2} + R ^ 0_ {2,1} {R ^ 0_ {1,1}} ^ * R ^ 0_ {1,2} = ε + b ε ^ * a = ε + ba $.
Dlaczego tak jest? Dzieje się tak, ponieważ przejście z $ q_2 $ do $ q_2 $ przy użyciu tylko $ q_1 $ jako stanu pośredniego można zrobić, pozostając tutaj ($ ε $) lub przechodząc do $ q_1 $ ($ a $), zapętlając ($ ε ^ * $) i wracam ($ b $).
$$ R ^ 1 = \ begin {bmatrix} ε & a & b \\ b & ε + ba & a + bb \\ a & b + aa & ε + ab \ end {bmatrix} $$
Możesz obliczyć w ten sposób $ R ^ 2 $ i $ R ^ 3 $, a także $ R ^ 3_ {1,1 } $ da ci końcowe wyrażenie, ponieważ $ 1 $ jest zarówno początkiem, jak i końcem. Zwróć uwagę, że wprowadzono tutaj wiele uproszczeń wyrażeń. W przeciwnym razie pierwszym $ a $ z $ R ^ 0 $ byłoby $ (∅ + a) $, a pierwszym $ a $ z $ R ^ 1 $ byłoby $ ((∅ + a) + ε (ε) ^ * a ) $.
Algorytm
Inicjalizacja:
for i = 1 to n: for j = 1 to n: if i == j: R[i,j,0] := ε else: R[i,j,0] := ∅ for a in Σ: if trans(i, a, j): R[i,j,0] := R[i,j,0] + a
Zamknięcie przechodnie:
for k = 1 to n: for i = 1 to n: for j = 1 to n: R[i,j,k] := R[i,j,k-1] + R[i,k,k-1] . star(R[k,k,k-1]) . R(k,j,k-1)
Zatem końcowe wyrażenie to (zakładając, że $ q_s $ jest stanem początkowym):
e := ∅ for i = 1 to n: if final(i): e := e + R[s,i,n]
Ale możesz sobie wyobrazić generuje brzydkie wyrażenia regularne. Rzeczywiście możesz spodziewać się rzeczy takich jak $ (∅) ^ * + (a + (∅) ^ *) (ε) ^ * (a + ∅) $, które reprezentują ten sam język co $ aa $. Zwróć uwagę, że uproszczenie wyrażenia regularnego jest przydatne w praktyce.
Dodaj komentarz