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

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 i chcemy usunąć . $p,q,r$ $e,f,g,h,i$ $q$

automat pqr

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

wprowadź opis zdjęcia tutaj

Przykład

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

Automat 1-2-3

sukcesywnie usuwamy : $q_2$

Automat 1-3

a następnie : $q_3$

1 automat

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

(a b + (b + a a) (b a)^{*} (a + b b))^{*}

$(ab+(b+aa)(ba)^*(a+bb))^*$

Algorytm

L[i,j]to wyrażenie regularne języka od do . 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 a lub i ) $∅$ $ε$ $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 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 zakładając że jest jedynym stanem początkowym jest jedynym stanem końcowym, następnie robi unii wszystkich . $(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.

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

ε

$\varepsilon$ 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

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

do

q^{+}

$q^+$

q^{-}

$q^-$

ε

$\varepsilon$

q^{+}

$q^+$

. Konstrukcja nie da pętli przy

lub

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.

q_{-}

$q_-$

q^{+}

$q^+$

q_{-}

$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 NFA $A= (Q,\Sigma,\delta,q_0,F)$ przejścia. Dla każdego stanu 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 oznacza przejście od do oznaczonego . 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 Ardena ¹: $\cup$ $\cdot$ $\cup$

Niech języków regularnych z . 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 . opisuje dokładnie te słowa, które mogą być zaakceptowane przez kiedy rozpoczęła się w ; dlatego (jeśli 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:

przykład 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 , i . Zauważ, że wszystkie trzy języki są regularne i , 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.

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

jest stanem końcowym.

Q_{i}

$Q_i$

q_{0}

$q_0$

— 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 możemy uznać automat za zbiór równań formy: $X=A^*B$ $X=AX∪B$

X_{i} = B_{i} + A_{i, 1} X_{1} + \dots + A_{i, n} X_{n}

$X_i = B_i + A_{i,1}X_1 + … + A_{i,n}X_n$

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

X_{n} = B_{n} + A_{n, 1} X_{1} + \dots + A_{n, n} X_{n}

$X_n = B_n + A_{n,1}X_1 + … + A_{n,n}X_n$

a reguła Ardena daje nam:

X_{n} = A_{n, n}^{*} (B_{n} + A_{n, 1} X_{1} + \dots + A_{n, n - 1} X_{n - 1})

$X_n = A_{n,n}^* (B_n + A_{n,1}X_1 + … + A_{n,n-1}X_{n-1})$

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

X_{n} = B_{n}^{'} + A_{n, 1}^{'} X_{1} + \dots + A_{n, n - 1}^{'} X_{n - 1}

$X_n = B'_n + A'_{n,1}X_1 + … + A'_{n,n-1}X_{n-1}$

$X_n$ $i,j<n$

B_{i}^{'} = B_{i} + A_{i, n} B_{n}^{'}

$B'_i = B_i + A_{i,n}B'_n$

A_{i, j}^{'} = A_{i, j} + A_{i, n} A_{n, j}^{'}

$A'_{i,j} = A_{i,j} + A_{i,n}A'_{n,j}$

$X_n$ $n=1$

X_{1} = B_{1}^{'}

$X_1 = B'_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.

— 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ł

$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_{i, j}^{'} = R_{i, j} + R_{i, k} . R_{k, k}^{*} . R_{k, j}

$R'_{i,j} = R_{i,j} + R_{i,k} . R_{k,k}^* . R_{k,j}$

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

R^{0} = [\begin{matrix} ε & a & b \\ b & ε & a \\ a & b & ε \end{matrix}]

$R^0 = \begin{bmatrix} ε & a & b \\ b & ε & a \\ a & b & ε \end{bmatrix}$

$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^{1} = [\begin{matrix} ε & a & b \\ b & ε + b a & a + b b \\ a & b + a a & ε + a b \end{matrix}]

$R^1 = \begin{bmatrix} ε & a & b \\ b & ε+ba & a+bb \\ a & b+aa & ε+ab \end{bmatrix}$

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

— jmad
źródło

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

Metoda usuwania stanu

Kluczowy pomysł

Przykład

Algorytm

Cons

metoda

Przykład

Metoda algebraiczna Brzozowskiego

Idea algorytmu

Algorytm

Realizacja

Metoda zamknięcia przechodniego

Kluczowy pomysł

Przykład

Algorytm