Jak przekonwertować skończone automaty na wyrażenia regularne?

115

Konwersja wyrażeń regularnych na (minimalne) NFA, które akceptują ten sam język, jest łatwa dzięki standardowym algorytmom, np . Algorytmowi Thompsona . Drugi kierunek wydaje się jednak bardziej nużący, a czasem wynikowe wyrażenia są nieuporządkowane.

Jakie są algorytmy przekształcania NFA w równoważne wyrażenia regularne? Czy są zalety dotyczące złożoności czasu lub wielkości wyniku?

To ma być pytanie referencyjne. Podaj ogólną opis swojej metody, a także nietrywialny przykład.

Raphael
źródło
2
Zwróć uwagę na podobne pytanie na cstheory.SE, które prawdopodobnie nie jest odpowiednie dla naszych odbiorców.
Raphael
wszystkie odpowiedzi wykorzystują technikę formalną do pisania RE z DFA. Wierzę, że moja technika analizy jest stosunkowo łatwa i obiektywna, co pokazuję w odpowiedzi: Jaki jest język tych deterministycznych automatów skończonych? Czuję, że kiedyś byłoby to pomocne. Tak, oczywiście, że czasami sam używam metody formalnej (twierdzenie Arden) do pisania RE jest pytaniem złożonym, jak podano w tym przykładzie: Jak napisać wyrażenie regularne dla DFA
Grijesh Chauhan

Odpowiedzi:

94

Istnieje kilka metod konwersji z automatów skończonych na wyrażenia regularne. Tutaj opiszę ten, którego zwykle uczy się w szkole, który jest bardzo wizualny. Uważam, że jest najczęściej używany w praktyce. Jednak napisanie algorytmu nie jest tak dobrym pomysłem.

Metoda usuwania stanu

Algorytm ten dotyczy obsługi wykresu automatu i dlatego nie jest zbyt odpowiedni dla algorytmów, ponieważ wymaga prymitywów grafowych, takich jak ... usunięcie stanu. Opiszę to za pomocą prymitywów wyższego poziomu.

Kluczowy pomysł

Chodzi o rozważenie wyrażeń regularnych na krawędziach, a następnie usunięcie stanów pośrednich przy zachowaniu spójności etykiet krawędzi.

Główny wzór można zobaczyć poniżej na rysunkach. Pierwszy ma etykiety między które są wyrażeniami regularnymi e , f , g , h , i, i chcemy usunąć q .p,q,re,f,g,h,iq

automat pqr

Po usunięciu składamy razem (zachowując pozostałe krawędzie między p i r, ale nie jest to wyświetlane na tym):e,f,g,h,ipr

wprowadź opis zdjęcia tutaj

Przykład

Korzystając z tego samego przykładu, co w odpowiedzi Raphaela :

Automat 1-2-3

sukcesywnie usuwamy :q2

Automat 1-3

a następnie :q3

1 automat

wtedy nadal musimy zastosować gwiazdkę do wyrażenia od do q 1 . W tym przypadku stan końcowy jest również początkowy, więc naprawdę wystarczy dodać gwiazdkę:q1q1

(ab+(b+aa)(ba)(a+bb))

Algorytm

L[i,j]to wyrażenie regularne języka od do q j . Najpierw usuwamy wszystkie krawędzie:qiqj

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

Teraz usunięcie stanu. Załóżmy, że chcemy usunąć stan :qk

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]

Należy zauważyć, że zarówno z ołówkiem papieru i algorytmu należy uprościć wyrażenia jak star(ε)=ε, e.ε=e, ∅+e=e, ∅.e=∅(ręcznie po prostu nie pisać krawędź gdy nie lub nawet ε dla siebie pętli i zignorować, gdy istnieje brak przejścia między q i a q k lub q j i q k )εqiqkqjqk

Teraz, jak korzystać remove(k)? Nie powinieneś lekko usuwać stanów końcowych ani początkowych, w przeciwnym razie ominiesz część języka.

for i = 1 to n:
  if not(final(i)) and not(initial(i)):
    remove(i)

Jeśli masz tylko jeden ostateczny stan i jeden stan początkowy q s następnie ostateczne wyrażenie jest:qfaqs

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 połączenia tych stanów, oprócz zastosowania metody zamykania przechodniego. Zwykle nie jest to problem ręcznie, ale jest to niewygodne podczas pisania algorytmu. Znacznie prostszym obejściem jest wyliczenie wszystkich par i uruchomienie algorytmu na wykresie (już usuniętym przez stan), aby uzyskać wszystkie wyrażenia e s , f zakładając , że s jest jedynym stanem początkowym if jest jedynym stanem końcowym, następnie robi unii wszystkich e s , f .(s,f)es,fsfes,f

To oraz fakt, że modyfikuje języki bardziej dynamicznie niż pierwsza metoda, czyni go bardziej podatnym na błędy podczas programowania. Sugeruję użycie innej metody.

Cons

Algorytm zawiera wiele przypadków, na przykład wybór węzła, który należy usunąć, liczbę 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 zapisany, przypomina to metodę zamykania przechodniego. Jedynie kontekst użytkowania jest inny. Nie polecam implementacji algorytmu, ale dobrym pomysłem jest użycie metody ręcznej.

jmad
źródło
1
W przykładzie drugi obraz, po usunięciu węzła „2”, brakuje krawędzi - pętli krawędzi (ab) w węźle A.
Panos Kal.
@Kabamaru: Naprawiono. Ale teraz myślę, że na trzecim obrazie również powinna być , i podobnie być może w końcowym wyrażeniu regularnym. εab
Wandering Logic
Możesz sprawić, by algorytm działał dla dowolnej liczby stanów początkowych i końcowych, dodając nowy początkowy stan i nowy stan końcowy q - oraz łącząc je z oryginalnymi stanami początkowymi i końcowymi za pomocą krawędzi ε . Teraz usuń wszystkie oryginalne stany. Następnie wyrażenie znajduje się na pojedynczej pozostałej krawędzi od q + doq+qεq+ . Konstrukcja nie da pętli przy q + lub q - ponieważ te stany nie mają odpowiednio wstępnych. krawędzie wychodzące. Lub jeśli jesteś surowy, będą miały etykiety reprezentujące pusty zestaw. qq+q
Hendrik Jan
1
W drugim przykładzie nadal występuje problem: przed uproszczeniem automaty akceptują „ba”, (1, 3, 1), ale po uproszczeniu tak nie jest.
wvxvw,
50

metoda

Najładniejszą metodą, jaką widziałem, jest ta, która wyraża automat jako układ równań (zwykłych) języków, które można rozwiązać. Jest to szczególnie miłe, ponieważ wydaje się przynosić bardziej zwięzłe wyrażenia niż inne metody.

Niech bez NFAA=(Q,Σ,δ,q0,F) przejścia. Dla każdego stanu q i utwórz równanieεqi

Qi=qiaqjaQj{{ε}, qiF, else

gdzie jest zbiorem stanów końcowych, a q i a q j oznacza przejście od q i do q j oznaczonego a . Jeśli czytasz jako + lub (w zależności od definicji wyrażenia regularnego), zobaczysz, że jest to równanie wyrażeń regularnych.Fqiaqjqiqja+

Do rozwiązania systemu potrzebujesz asocjatywności i dystrybucji i (konkatenacji łańcuchów), komutatywności i Lemmy Ardena ¹:

Niech języków regularnych z ε U . Następnie,L,U,VΣεU

L=ULVL=UV

Rozwiązaniem jest zbiór wyrażeń regularnych , po jednym dla każdego stanu q í . Q i opisuje dokładnie te słowa, które mogą być zaakceptowane przez A kiedy rozpoczęła się w q í ; dlatego Q 0 (jeśli q 0 jest stanem początkowym) jest pożądanym wyrażeniem.QiqiQiAqiQ0q0


Przykład

Dla jasności oznaczamy zestawy singletonów według ich elementu, tj. . Ten przykład należy do Georga Zetzschego.a={a}

Rozważ to NFA:

przykład nfa
[ źródło ]

Odpowiedni układ równań to:

Q0=aQ1bQ2εQ1=bQ0aQ2Q2=aQ0bQ1

Teraz podłącz trzecie równanie do drugiego:

Q1=bQ0a(aQ0bQ1)=abQ1(baa)Q0=(ab)(baa)Q0

Na ostatnim etapie stosujemy Arden lematu z , u = a , b i V = ( b a ) Q 0 . Zauważ, że wszystkie trzy języki są regularne i ε U = { a b } , co pozwala nam zastosować lemat. Teraz wstawiamy ten wynik do pierwszego równania:L=Q1U=abV=(baa)Q0εU={ab}

Q0=a(ab)(baa)Q0baQ0bb(ab)(baa)Q0ε=((abb)(ab)(baa)ba)Q0ε=((abb)(ab)(baa)ba)(by Arden's Lemma)

Tak więc znaleźliśmy wyrażenie regularne dla języka akceptowanego przez powyższy automat, mianowicie

((a+bb)(ab)(b+aa)+ba).

Zauważ, że jest dość zwięzły (porównaj z wynikiem innych metod), ale nie jest jednoznacznie określony; rozwiązanie układu równań z inną sekwencją manipulacji prowadzi do innych - równoważnych! - wyrażenia.


  1. Dowód lematu Ardena znajduje się tutaj .
Raphael
źródło
1
Jaka jest złożoność czasowa tego algorytmu? Czy istnieje ograniczenie wielkości wytwarzanego wyrażenia?
jmite
@jmite: Nie mam pojęcia. Nie sądzę, żebym próbował to zaimplementować (inne metody wydają się bardziej wykonalne w tym względzie), ale używam go jako metody papierowej.
Raphael
1
Oto implementacja tego algorytmu w Prologu: github.com/wvxvw/intro-to-automata-theory/blob/master/automata/…, ale jego maybe_union/2predykat może wymagać więcej pracy (zwłaszcza wrt eliminując wspólny przedrostek), aby uzyskać bardziej regularne wyrażenia regularne. Innym sposobem postrzegania tej metody jest zrozumienie jej jako tłumaczenia z wyrażenia regularnego na gramatykę liniowo-prawą, gdzie języki z ujednoliceniem przypominającym Prolog lub dopasowaniem wzorców podobnym do ML tworzą bardzo dobre przetworniki, więc nie są to tylko kartki algorytm :)
wvxvw,
Tylko jedno pytanie. Ε w pierwszym równaniu jest spowodowane tym, że Qo jest stanem początkowym, czy dlatego, że jest to stan końcowy? Ten sam sposób dotyczy dwóch końcowych stanów?
Georgio3
@PAOK Sprawdź definicję powyżej (linia); to dlatego, że q 0 jest stanem końcowym. Qiq0
Raphael
28

Metoda algebraiczna Brzozowskiego

Jest to ta sama metoda, którą opisano w odpowiedzi Raphaela , ale z punktu widzenia algorytmu systematycznego, a następnie algorytmu. Okazuje się, że wdrożenie jest łatwe i naturalne, gdy wiesz, od czego zacząć. Może być również łatwiejsze ręczne, jeśli rysowanie wszystkich automatów jest z jakiegoś powodu niepraktyczne.

Pisząc algorytm, należy pamiętać, że równania muszą być zawsze liniowe, aby uzyskać dobrą abstrakcyjną reprezentację równań, o czym można zapomnieć, rozwiązując ręcznie.

Idea algorytmu

Nie opiszę, jak to działa, ponieważ dobrze to zrobiono w odpowiedzi Raphaela, którą sugeruję przeczytać wcześniej. Zamiast tego skupiam się na tym, w jakiej kolejności należy rozwiązywać równania bez wykonywania zbyt wielu dodatkowych obliczeń lub dodatkowych przypadków.

Począwszy od genialnego rozwiązania reguły Ardena do równania językowego X = A X B możemy uznać automat za zbiór równań formy:X=ABX=AXB

Xi=Bi+Ai,1X1++Ai,nXn

możemy rozwiązać ten problem przez indukcję na aktualizując tablice i , j oraz B : i , j odpowiednio. W kroku n mamy:nAi,jBi,jn

Xn=Bn+An,1X1++An,nXn

a reguła Ardena daje nam:

Xn=An,n(Bn+An,1X1++An,n1Xn1)

Bn=An,nBnAn,i=An,nAn,i

Xn=Bn+An,1X1++An,n1Xn1

Xni,j<n

Bi=Bi+Ai,nBn
Ai,j=Ai,j+Ai,nAn,j

Xnn=1

X1=B1

A1,i

Algorytm

q1mB

for i = 1 to m:
  if final(i):
    B[i] := ε
  else:
    B[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]

Realizacja

Nawet jeśli może się to wydawać układem równań, który wydaje się zbyt symboliczny dla algorytmu, ten doskonale nadaje się do implementacji. Oto implementacja tego algorytmu w Ocaml (uszkodzony link) . Zauważ, że oprócz funkcji brzozowskiwszystko służy do wydrukowania lub użycia w przykładzie Raphaela. Zauważ, że istnieje zaskakująco skuteczna funkcja uproszczenia wyrażeń regularnych simple_re.

jmad
źródło
4
Link nie działa ...
Columbo,
Implementacja w JavaScript: github.com/devongovett/regexgen/blob/master/src/regex.js
cakraww
24

Metoda zamknięcia przechodniego

Ta metoda jest łatwa do zapisania w formie algorytmu, ale generuje absurdalnie duże wyrażenia regularne i jest niepraktyczna, jeśli robisz to ręcznie, głównie dlatego, że jest to zbyt systematyczne. Jest to jednak dobre i proste rozwiązanie dla algorytmu.

Kluczowy pomysł

Ri,jkqiqj{q1,,qk}n

Ri,jqiqjqki,jRi,jqk

Ri,j=Ri,j+Ri,k.Rk,k.Rk,j

RRk1RRk

Przykład

Użyjemy tego samego przykładu, co w odpowiedzi Rafaela . Na początku możesz używać tylko bezpośrednich przejść.

aε(ε+a)

R0=[εabbεaabε]

q0q1R0R1

q2q2R2,21=R2,20+R2,10R1,10R1,20=ε+bεa=ε+ba

q2q2q1εq1aεb

R1=[εabbε+baa+bbab+aaε+ab]

R2R3R1,131aR0(+a)aR1((+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

Przejściowe zamknięcie:

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)

qs

e := ∅
for i = 1 to n:
  if final(i):
    e := e + R[s,i,n]

()+(a+())(ε)(a+)aa

jmad
źródło