Konwersja automatu na wyrażenie regularne

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

Opis algorytmu

Na wejściu mamy pewien NKA A. Pierwszą rzeczą, którą robimy, jest przekształcenie go w ZNKA. W drugim etapie usuwamy jeden stan na raz w jednym kroku, poprawnie modyfikujemy funkcje przejścia i powtarzamy, aż pozostaną tylko dwa stany, początkowy i końcowy. Pomiędzy nimi poprowadzimy krawędź, która będzie wyrażeniem regularnym jako etykietą, która będzie wynikiem całego algorytmu. Tak więc cała procedura polega przede wszystkim na usunięciu stanu, a następnie naprawie automatu w celu uzyskania równoważnego automatu.

Usuwanie jednego stanu

Sposób usuwania pojedynczego stanu możemy zilustrować na prostym przykładzie. Załóżmy, że część naszego automatu wygląda następująco:

gdzie R_i to wyrażenia regularne. Jak wyglądałby automat, gdybyśmy usunęli stan q_r? Możemy sobie wyobrazić, że znajdujemy się w stanie q_i i pytamy, jakie słowa jesteśmy w stanie wygenerować w tej sekcji? Jeśli przejdziemy ze stanu q_i bezpośrednio do stanu q_j, będą to wszystkie słowa pasujące do wyrażenia regularnego R₄.

Ale jeśli przejdziemy do stanu q_r, możemy wygenerować słowa w postaci R₁. Ale w stanie q_r możemy cyklicznie dla wyrażenia regularnego R₂, więc możemy faktycznie wygenerować słowa w postaci $R_1\circ(R_2^\ast)$. Cóż, ponieważ nadal możemy przejść ze stanu q_r do stanu q_j, możemy dodać wyrażenie regularne R₃. Ogólnie rzecz biorąc, możemy w ten sposób uzyskać słowa w postaci $R_1\circ(R_2^\ast)\circ R_3$.

Teraz wiemy, że ta część automatu może produkować słowa w postaci R₄ lub $R_1\circ(R_2^\ast)\circ R_3$. Oczywiście możemy zapisać to w postaci wyrażenia regularnego, takiego jak $(R_4)|(R_1\circ(R_2^\ast)\circ R_3)$.

Teraz możemy po prostu usunąć stan q_r i pozostawić tylko dwa stany q_i i q_j i zapisać wyrażenie regularne, które właśnie obliczyliśmy zamiast R₄:

Robimy to z każdą krawędzią od każdego stanu q_i do jakiegoś stanu q_j i włączając pętle, tj. włączając przypadek, w którym q_i = q_j.

Po usunięciu jednego stanu otrzymujemy równoważny automat - automat rozpoznający ten sam język.

Cały algorytm

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

1. Konwertujemy NKA A na ZNKA $Z=\left<Q^\prime, \Sigma, \delta^\prime, q_0^\prime, q_f^\prime\right>$. Następnie użyjemy litery k do oznaczenia liczby stanów w Z.
2. Jeśli k = 2, algorytm kończy działanie, a krawędź między stanem początkowym i końcowym jest wynikowym wyrażeniem regularnym.
3. Jeśli k>2, wybieramy dowolny stan q_r, który różni się od stanu początkowego i końcowego, tj. $q_r\ne q_0^\prime$ i $q_r\ne q_f^\prime$. Następnie tworzymy nową ZNKA $Z^\prime=\left<Q^{\prime\prime}, \Sigma, \delta^{\prime\prime},q_0^{\prime},q_f^{\prime}\right>$, dla której będzie ona ważna: $$ 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\}$ i 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)$. Przejdź do kroku 2.

Przykład

Rozważmy następujący automat skończony jako dane wejściowe:

Najpierw przekształcamy go w ZNKA (nie będziemy pokazywać niepotrzebnych ∅-transitions):

Teraz stosujemy drugą część algorytmu i usuwamy węzeł. Zaczynamy od węzła q₂. Usuwamy węzeł q₂ i dodajemy przejście ze stanu q₁ do stanu q_f. Przejście to oznaczymy jako $b(a|b)^\ast$, ponieważ z węzła q₁ przechodzimy do stanu q₂ dla słów o postaci b, następnie możemy przejść do a|b, uzyskując $(a|b)^\ast$, a na koniec, korzystając z reguły epsilon, przechodzimy do q_f. W ten sposób uzyskujemy $b(a|b)^\ast\epsilon=b(a|b)^\ast$. Otrzymujemy automat:

Pozostaje nam usunięcie ostatniego stanu, q₁. Dodajemy krawędź ze stanu q_s do stanu q_f. Jak ją oznaczyć? Możemy dostać się do stanu q₁ poprzez regułę epsilon, możemy ją po prostu porzucić. Następnie możemy wykonać cykl dla a, więc otrzymamy wyrażenie regularne $a^\ast$. Cóż, w końcu dotrzemy do q_f przez krawędź, więc połączymy wyrażenie z $b(a|b)^\ast$. Więc opiszemy krawędź wyrażeniem regularnym $a^\ast b(a|b)^\ast$.

Automat ma jeszcze tylko dwa stany, więc algorytm się kończy. Krawędź jest wynikowym wyrażeniem regularnym.

Zasoby

• Przykład i opis algorytmu pochodzą z książki M. Sipser: Introduction to the Theory of Computation.