✖

Przekształcenie automatu w wyrażenie regularne

Kapitoly: Wyrażenia regularne, Wyrażenie regularne na automat, Uogólniony NFA, Automat na wyrażenie regularne

Pokażemy, jak przekształcić dowolny automat skończony w wyrażenie regularne.

Opis algorytmu

Na wejściu mamy jakiś NFA A. Najpierw zrobimy z niego GNFA. W drugiej fazie w każdym kroku usuniemy jeden stan, odpowiednio zmienimy funkcję przejścia i powtórzymy to, dopóki nie zostaną tylko dwa stany – początkowy i akceptujący. Między nimi będzie prowadzić krawędź, której etykietą będzie wyrażenie regularne będące wynikiem całego algorytmu. Całe postępowanie polega więc przede wszystkim na usunięciu stanu i następnie takiej poprawie automatu, żebyśmy dostali automat równoważny.

Usunięcie jednego stanu

Jak usunąć jeden stan, pokażemy na prostym przykładzie. Załóżmy, że część naszego automatu wygląda tak:

gdzie Ri to jakieś wyrażenia regularne. Jak wyglądałby automat, gdybyśmy usunęli stan qr? Możemy to sobie wyobrazić tak, że jesteśmy w stanie qi i pytamy, jakie słowa w ogóle możemy na tym odcinku wygenerować. Jeśli pójdziemy ze stanu qi prosto do stanu qj, będą to wszystkie słowa, które pasują do wyrażenia regularnego R4.

Jeśli jednak pójdziemy do stanu qr, możemy wygenerować słowa postaci R1. W stanie qr możemy jednak krążyć w pętli dla wyrażenia regularnego R2, więc właściwie możemy wygenerować słowa postaci $R_1\circ(R_2^\ast)$. A ponieważ możemy jeszcze przejść ze stanu qr do stanu qj, dodamy jeszcze wyrażenie regularne R3. Łącznie tą drogą możemy więc dostać słowa postaci $R_1\circ(R_2^\ast)\circ R_3$.

Teraz wiemy, że z tej części automatu mogą powstać słowa postaci R4 albo postaci $R_1\circ(R_2^\ast)\circ R_3$. To oczywiście możemy zapisać w postaci wyrażenia regularnego jako $(R_4)|(R_1\circ(R_2^\ast)\circ R_3)$.

Teraz już możemy po prostu usunąć stan qr, zostawić tylko dwa stany qi i qj, a zamiast R4 wpisać właśnie obliczone wyrażenie regularne:

To postępowanie przeprowadzimy z każdą krawędzią z każdego stanu qi do jakiegoś stanu qj, i to łącznie z pętlami, czyli także w przypadku, gdy qi = qj.

Po usunięciu jednego stanu dostaniemy automat równoważny – automat, który rozpoznaje ten sam język.

Cały algorytm

Na wejściu mamy NFA $A=\left<Q, \Sigma, \delta, q_0, F\right>$.

  1. Przekształcimy NFA A w GNFA $Z=\left<Q^\prime, \Sigma, \delta^\prime, q_0^\prime, q_f^\prime\right>$. Dalej literą k będziemy oznaczać liczbę stanów w Z.
  2. Jeśli k = 2, algorytm się kończy, a na krawędzi między stanem początkowym i akceptującym jest wynikowe wyrażenie regularne.
  3. Jeśli k>2, wybierzemy dowolny stan qr, który jest różny od stanu początkowego i akceptującego, czyli $q_r\ne q_0^\prime$ i $q_r\ne q_f^\prime$. Dalej utworzymy nowy GNFA $Z^\prime=\left<Q^{\prime\prime}, \Sigma, \delta^{\prime\prime},q_0^{\prime},q_f^{\prime}\right>$, dla którego będzie zachodzić: $$ Q^{\prime\prime}=Q^\prime\setminus\left\{q_r\right\} $$ i dla wszystkich $q_i\in Q^{\prime\prime}\setminus\left\{q_f^\prime\right\}$ oraz dla wszystkich $q_j\in Q^{\prime\prime}\setminus \left\{q_0^\prime\right\}$ niech $$ \delta^{\prime\prime}(q_i, q_j)=(R_4)|(R_1(R_2^\ast)R_3), $$ gdzie $R_1=\delta^\prime(q_i,q_r)$, $R_2=\delta^\prime(q_r,q_r)$, $R_3=\delta^\prime(q_r, q_j)$, $R_4=\delta^\prime(q_i, q_j)$. Dalej przejdź do kroku 2.

Przykład

Weźmy na wejściu taki automat skończony:

Najpierw przekształcimy go w GNFA (zbędnych ∅-przejść nie będziemy rysować):

Teraz zastosujemy drugą część algorytmu i usuniemy jakiś węzeł. Zaczniemy od węzła q2. Usuniemy węzeł q2 i dodamy przejście ze stanu q1 do stanu qf. To przejście opiszemy jako $b(a|b)^\ast$, bo z węzła q1 dostaniemy się do stanu q2 dla słów postaci b, potem możemy krążyć w pętli dla a|b, przez co dostaniemy $(a|b)^\ast$, a na koniec za pomocą epsilon-przejścia przeniesiemy się do qf. Przy tym zachodzi $b(a|b)^\ast\epsilon=b(a|b)^\ast$. Dostaniemy automat:

Zostaje nam usunąć ostatni stan, q1. Dodamy krawędź ze stanu qs do stanu qf. Jak ją opiszemy? Do stanu q1 dostaniemy się przez epsilon-przejście, które możemy od razu pominąć. Potem możemy krążyć w pętli dla a, więc dostaniemy wyrażenie regularne $a^\ast$. A na koniec przez krawędź dostaniemy się do qf, więc na końcu wyrażenia dopiszemy jeszcze $b(a|b)^\ast$. Krawędź opiszemy więc wyrażeniem regularnym $a^\ast b(a|b)^\ast$.

Automat ma już tylko dwa stany, więc algorytm się kończy. Na krawędzi jest wynikowe wyrażenie regularne.

Źródła