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.}

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,r$$e,f,g,h,i$$q$

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,i$$p$$r$

Przykład

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

sukcesywnie usuwamy :$q_2$

a następnie :$q_3$

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ę:$q_1$$q_1$

Algorytm

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

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 :$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]

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 )$∅$$ε$$q_i$$q_k$$q_j$$q_k$

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:$q_f$$q_s$

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)$$e_{s,f}$$s$$f$$e_{s,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.

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 NFA$A= (Q,\Sigma,\delta,q_0,F)$ przejścia. Dla każdego stanu q i utwórz równanie$\varepsilon$$q_i$

$\qquad \displaystyle Q_i = \bigcup\limits_{q_i \overset{a}{\to} q_j} aQ_j \cup \begin{cases} \{\varepsilon\} &,\ q_i \in F \\ \emptyset &, \text{ else}\end{cases}$

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.$F$$q_i \overset{a}{\to} q_j$$q_i$$q_j$$a$$\cup$$+$$\mid$

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

Niech języków regularnych z ε ∉ U . Następnie,$L,U,V \subseteq \Sigma^*$$\varepsilon \notin U$

$\qquad \displaystyle L = UL \cup V \quad \Longleftrightarrow \quad L = U^*V$

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.$Q_i$$q_i$$Q_i$$A$$q_i$$Q_0$$q_0$

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:

^{[ ź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}$

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 = Q_1$$U = ab$$V = (b \cup aa) \cdot Q_0$$\varepsilon \notin U = \{ab\}$

$\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{(by Arden's Lemma)} \end{align}$

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

$\qquad \displaystyle ((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 .

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=A^*B$$X=AX∪B$

możemy rozwiązać ten problem przez indukcję na aktualizując tablice i , j oraz B : i , j odpowiednio. W kroku n mamy:$n$$A_{i,j}$$B_{i,j}$$n$

a reguła Ardena daje nam:

$B'_n = A_{n,n}^* B_n$$A'_{n,i}=A_{n,n}^*A_{n,i}$

$X_n$$i,j<n$

$X_n$$n=1$

$A'_{1,i}$

Algorytm

$q_1$$m$$B$

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.

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ł

$R^k_{i,j}$$q_i$$q_j$$\{q_1, …, q_k\}$$n$

$R_{i,j}$$q_i$$q_j$$q_k$$i,j$$R'_{i,j}$$q_k$

$R$$R^{k-1}$$R'$$R^k$

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)$

$q_0$$q_1$$R^0$$R^1$

$q_2$$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$

$q_2$$q_2$$q_1$$ε$$q_1$$a$$ε^*$$b$

$R^2$$R^3$$R^3_{1,1}$$1$$a$$R^0$$(∅+a)$$a$$R^1$$((∅+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)

$q_s$

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

$(∅)^*+(a+(∅)^*)(ε)^*(a + ∅)$$aa$