Wyrażenia regularne a algorytm Floyda-Warshalla

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”

Bartosz says:

01/04/2022 at 20:44

Dziękuję za ten post i życzę powodzenia w pisaniu kolejnych!

1. framal says:
  
  02/04/2022 at 17:30
  
  Dziękuję 🙂
  
Kamil says:

17/04/2022 at 13:37

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 😀

Michał says:

11/05/2022 at 20:29

nice

1. framal says:
  
  11/05/2022 at 20:30
  
  nice

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

Leave a Reply Cancel reply