Wyrażenia regularne a algorytm Floyda-Warshalla

Krótka notatka o fajnym połączeniu między dwoma światami

Na jednych z pierwszych zajęć JFiZO został przedstawiony konstruktywny dowód na równoważność siły wyrażeń regularnych oraz deterministycznych automatów skończonych (DFA). Pokazanie, że dla każdego regexa istnieje równoważny DFA jest proste, sprawa komplikuje się w drugą stronę. Tak mi się przynajmniej na początku wydawało, ale im dłużej o tym myślałem, tym bardziej odczuwałem wrażenie, że gdzieś już ten dowód widziałem.

Tutaj można sobie zobaczyć moje notatki z JFiZO i nie tylko.

Dla ustalenia uwagi napiszę przyjmowane przeze mnie definicje (jeżeli jesteś z tym zaznajomiony, to przewiń do końca artykułu):

Definicja 1. Deterministycznym automatem skończonym (DFA) nazywamy krotkę A = \langle \Sigma, Q, q_0, \delta, F\rangle, gdzie \Sigma to skończony alfabet, Q to skończony zbiór stanów, q_0 to stan początkowy, \delta\colon Q\times\Sigma\to Q to funkcja przejścia oraz F\subseteq Q jest zbiorem stanów akceptujących.

Definicja 2. \phi nazywamy wyrażeniem regularnym oraz L_\phi\subseteq\Sigma^* językiem, które wyraża to wyrażenie, gdy:

  • \phi\colon \emptyset oraz L_\emptyset = \emptyset,
  • \phi\colon \epsilon oraz L_\epsilon = \epsilon,
  • \phi\colon a, gdzie a\in\Sigma,
  • \phi\colon\phi_1 \phi_2, gdzie \phi_1, \phi_2 to wyrażenia regularne, wtedy L_\phi = L_\phi_1 L_\phi_2 (chodzi tu o konkatenację),
  • \phi\colon \phi_1 + \phi_2, gdzie \phi_1, \phi_2 to wyrażenia regularne, wtedy L_\phi = L_\phi_1\cup L_\phi_2 (czyli słowo pasuje do jednego lub do drugiego regexa),
  • \phi\colon \psi^*, wtedy L_\phi = L^*_\psi (gdzie L^* to zbiór skończonych konkatenacji słów
    z L).

Można zauważyć, że w definicji wyrażeń regularnych nie pojawia się kilka konstrukcji znanych z typowych regexów używanych w praktyce (często składnia się też trochę różni). Wynika to z kilku powodów, np. z tego że taka definicja jest w zupełności wystarczająca, inne są lukrem syntaktycznym (lub są niemożliwe do osiągnięcia, np. rejestry, co jest całkiem zabawne, bo takie wyrażenia przestają być regularne).

Przejdźmy do sedna, tj. do konstrukcji wyrażenia regularnego wyrażającego ten sam język, co dany DFA A. W zasadzie najciekawszy dla nas będzie początek dowodu, czyli pomysł na konstrukcję szukanego wyrażenia regularnego.

Twierdzenie. Niech A = \langle \Sigma, Q, q_0, \delta, F\rangle będzie DFA. Wtedy istnieje wyrażenie regularne \phi takie, że L_A=L_\phi, tj. zbiór słów akceptowanych przez automat jest dokładnie równy zbiorowi słów wyrażanych przez \phi.

Dowód. Niech Q = \{q_0, q_1,\ldots, q_{n-1}\}. Dla 0\le i, j\le n-1, -1\le k\le n-1 skonstruujemy wyrażenie regularne \phi^k_{i,j} wyrażające język

\{w\in\Sigma^*\colon \hat{\delta}(q_i, w) = q_j \, \wedge \forall v\in\Sigma^* \text{(jeśli }v\text{ jest właściwym prefiksem } w \text{ oraz } \hat{\delta}(q_i, v)=q_l \text{, to } l < k\text{)}\}

Uff, napis jest długi, więc postaram się go wyjaśnić bardziej opisowo. Chcemy, żeby \phi^k_{i,j} wyrażało tylko te słowa, które ze stanu q_i przechodzą do stanu q_j, a “po drodze” odwiedzają jedynie stany o numerach mniejszych niż k (nie bierzemy pod uwagę tutaj odwiedzin stanu początkowego i końcowego).

Powiedzmy, że dla wszystkich i, j, k mamy już takie wyrażenie regularne. Wtedy \displaystyle \phi = \bigoplus_{j\in F} \phi^{n-1}_{0, j} jest szukanym przez nas wyrażeniem regularnym. Konstrukcja tych wyrażeń następuje indukcyjnie względem k:

  • Dla k=-1 mamy \displaystyle\phi^{-1}_{i, i} = \epsilon + \bigoplus_{\substack{a\in\Sigma\\ \hat{\delta}(q_i, a) = q_i}} a, a dla i\neq j mamy \displaystyle\phi^{-1}_{i, j} =\bigoplus_{\substack{a\in\Sigma\\ \hat{\delta}(q_i, a) = q_j}} a. W skrócie: \phi^{-1}_{i,j} wyraża tylko te litery, którymi możemy bezpośrednio przejść z i-tego stanu do j-tego.
  • Załóżmy, że mamy już skonstruowane wyrażenia dla k. Będziemy teraz konstruować wyrażenia dla k+1. Zanim to zrobimy, zastanówmy się jak wyglądają słowa, które są wyrażane przez \phi^{k+1}_{i,j}. Jeszcze raz: chcemy wyrażać słowa w, które ze stanu q_i przeprowadzają nas do stanu q_j, a po drodze nie wchodzą do żadnego stanu o numerze większym niż k. Od razu widzimy, że na pewno słowa wyrażane przez \phi^k_{i,j} spełniają zadanie. Zostało nam zatem rozważać takie słowa, które na pewno przejdą przez stan q_k. Jak wygląda “ścieżka”, którą przesuwamy się idąc słowem w? Zaczynamy w stanie q_i, idziemy po kolejnych literach, aż w końcu po raz pierwszy trafiamy do q_k. Potem idziemy po kolejnych literach i potencjalnie kolejny raz trafiamy do q_k, aż w końcu ostatni raz odwiedzamy ten stan i przechodzimy bezpośrednio do q_j. To co teraz napiszę może wydawać się truizmem, ale jest bardzo istotne do dobrego zrozumienia konstrukcji: pomiędzy momentami odwiedzić stanu q_k nie odwiedzamy stanu q_k, a co za tym idzie — poruszamy się tylko po stanach o numerach mniejszych od k. Ale słowa, które w ten sposób przechodzą przez stany już potrafimy wyrażać! Możemy w końcu napisać:

    \[\displaystyle\phi^{k+1}_{i,j}= \phi^k_{i,j}+\phi^k_{i,k+1}(\phi^k_{k+1,k+1})^*\phi^k_{k+1,j}\]

\qed

Okej, ale co z tym Floydem-Warshallem? Przypomnijmy algorytm:

# Początkowe wartości w tablicy dist
for i in {1..n}
  for j in {1..n}
    dist[i, j] = infinity
  dist[i, i] = 0

# Obliczanie odległości
for k in {1..n}
  for i in {1..n}
    for j in {1..n}
      if dist[i, j] > dist[i, k] + dist[k, j]
        dist[i, j] = dist[i, k] + dist[k, j]

Czy to nie wygląda podobnie? Pomysł jest w zasadzie ten sam — dynamicznie “podnosimy możliwość” przechodzenia przez kolejne wierzchołki grafu. Ucieszyło mnie takie połączenie, tym bardziej że wzięło mnie trochę z zaskoczenia. Może komuś z Was też się spodoba.

Moja implementacja algorytmu konwersji DFA do wyrażeń regularnych w OCaml.

5 thoughts on “Wyrażenia regularne a algorytm Floyda-Warshalla”

  1. Dzięki za przypomnienie tego dowodu! To faktycznie ciekawe jak taka uporządkowana indukcja prowadzi do tak eleganckiego rozwiązania :3

    A myślę, że gdyby ten dynamik zapisać w stylu top-down (czyli rekurencyjnie ze spamiętywaniem) to nawet bardziej przypominałby technikę użytą w dowodzie 😀

Leave a Reply to framal Cancel reply

Your email address will not be published. Required fields are marked *