Automat skończony

Automat skończony (po angielsku finite state machine albo finite automaton) to model obliczeń prymitywnego komputera, który składa się z kilku stanów i kilku przejść i który potrafi zaakceptować albo odrzucić podane słowo.

Przykład

Nieformalnie opiszemy automat skończony za pomocą diagramu stanów, który go przedstawia:

Automat składa się ze stanów, na rysunku są to trzy okrągłe stany q₀, q₁ i q₂. Między tymi stanami są przejścia – to te strzałki. W automacie musi być jeszcze stan początkowy, tutaj jest to stan q₀. Stan początkowy często oznacza się tak, że prowadzi do niego strzałka, która nie wychodzi z żadnego stanu. Dalej w automacie zwykle jest stan akceptujący (końcowy), który rysujemy podwójną linią, więc na rysunku jest to stan q₂.

Tak zbudowany automat akceptuje pewne słowa. Podajemy automatowi jakieś słowa, a automat próbuje je zaakceptować. Jeśli je zaakceptuje, odpowie TAK, jeśli nie, odpowie NIE. Nasz automat próbuje akceptować słowa złożone z liter „a, b, c”, więc możemy spróbować słowa „abbc”.

Zaczynamy w stanie początkowym q₀, a na wejściu jest słowo „abbc”. Dalej będziemy podążać za strzałkami.

Słowo czytamy klasycznie od lewej do prawej, czyli jako pierwszy weźmiemy symbol „a”. Strzałka dla wejścia „a” prowadzi do stanu q₁, więc tam przechodzimy i usuwamy symbol „a” ze słowa. Na wejściu mamy teraz słowo „bbc”:

Strzałka dla wejścia „b” prowadzi z powrotem do węzła q₁. Znowu usuwamy pierwszą literę i na wejściu mamy słowo „bc”. Znowu zostajemy w stanie q₁. Na koniec mamy na wejściu słowo „c”. Ze stanu q₁ strzałka dla wejścia „c” wysyła nas do stanu q₂.

Wyczerpaliśmy już wszystkie litery słowa wejściowego i jesteśmy w stanie q₂, który jest stanem akceptującym. Ten automat skończony akceptuje więc słowo „abbc”.

Gdybyśmy na końcu nie byli w stanie akceptującym, automat nie zaakceptowałby słowa. Tak samo automat nie zaakceptowałby słowa, gdybyśmy w jakimś stanie nie mieli dokąd pójść. Na przykład dla wejścia „ab” dostalibyśmy się do stanu q₁ i tam byśmy skończyli – automat takiego słowa nie akceptuje. Gdybyśmy sprawdzili słowo „aabbc”, też mamy pecha, bo ze stanu q₁ nie wychodzi strzałka dla litery „a”.

Automat skończony służy więc do rozpoznawania pewnego zbioru słów. W praktyce moglibyśmy go użyć na przykład do sprawdzenia, czy dane słowo wejściowe jest poprawnym adresem e-mail.

Definicja automatu skończonego

Poprzednie intuicyjne wyobrażenie o tym, czym jest automat skończony, musimy sformalizować, żebyśmy mogli dalej i lepiej z automatami pracować.

Powiemy, że (deterministyczny) automat skończony to piątka $\left<Q, \Sigma, \delta, q_0, F\right>$, gdzie

• Q jest skończonym zbiorem stanów,
• $\Sigma$ (wielka sigma) jest alfabetem (skończonym zbiorem symboli/liter),
• $\delta: Q \times \Sigma\longrightarrow Q$ jest funkcją przejścia,
• q₀ ∈ Q jest stanem początkowym,
• F ⊆ Q jest zbiorem stanów akceptujących (końcowych).

Wracając do poprzedniego automatu,

możemy powiedzieć, że w zbiorze stanów Q są trzy stany Q = {q₀, q₁, q₂}. Alfabet $\Sigma$ zawiera litery, z których możemy składać słowa, które automat potem zaakceptuje albo odrzuci. Tutaj będzie to prawdopodobnie alfabet $\Sigma=\left\{a, b, c\right\}$, ale może to być też dowolny jego nadzbiór. Stanem początkowym q₀ jest stan q₀, tu nic się nie zmienia. Zbiór stanów akceptujących ma w tym automacie tylko jeden stan F = {q₂}.

Przez funkcję przejścia rozumiemy te trzy strzałki z literami. Jeśli myli cię zapis $\delta: Q \times \Sigma\longrightarrow Q$, to oznacza on tylko tyle, że δ jest funkcją (może lepiej odwzorowaniem), która przyjmuje dwa argumenty: stan z Q i literę z $\Sigma$. Po wywołaniu funkcja zwraca nowy stan. Naszą funkcję przejścia moglibyśmy zdefiniować tabelą tak:

$$ \begin{array}{cc|c} Q&\Sigma&\rightarrow Q\\\hline q_0&a&q_1\\ q_1&b&q_1\\ q_1&c&q_2\\ \end{array} $$

Jeśli więc wywołamy δ(q₁, c), zastosujemy trzeci wiersz i funkcja odpowie stanem q₂ – tak samo jak diagram. Jeśli jesteśmy w stanie q₁, a na wejściu jest litera „c”, przechodzimy do stanu q₂. Zanim formalnie zdefiniujemy, co znaczy, że automat akceptuje jakieś słowo, skorzystamy z intuicyjnego rozumienia tego pojęcia i pokażemy kilka kolejnych przykładów.

Kolejne przykłady

1. Zbuduj automat, który działa nad alfabetem binarnym, czyli $\Sigma=\left\{0,1\right\}$, i akceptuje tylko słowa kończące się jedynką. Akceptuje np. słowa 1, 01, 000001, 0101011.

   

   Nasz automat ma dwa stany – początkowy q₀ i akceptujący q₁. Ilekroć mamy na wejściu cyfrę 1, przechodzimy do stanu akceptującego q₁ i w nim zostajemy. I odwrotnie, jeśli na wejściu jest cyfra 0, przechodzimy do nieakceptującego stanu q₀ i też w nim zostajemy.

2. Zbuduj automat nad alfabetem binarnym, który akceptuje tylko słowa, których pierwsza litera jest różna od ostatniej.

   

   Automat już w pierwszym kroku dzieli się na dwa „podautomaty”. Jeśli słowo zaczyna się zerem, automat wchodzi do lewej części i już w niej zostaje; jeśli zaczyna się jedynką, przechodzi do prawej części. Dalej to już klasyka: jeśli jesteśmy w lewej części i na wejściu jest 1, przechodzimy do stanu akceptującego i tam zostajemy. Jeśli na wejściu jest 0, przechodzimy do stanu q₁, który akceptujący nie jest.

   W odróżnieniu od poprzednich automatów ten automat ma więcej stanów akceptujących, czyli F = {q₃, q₄}.

3. Zbuduj automat nad alfabetem binarnym, który akceptuje tylko słowa niezawierające dwóch zer pod rząd.

   

   Ten automat jest ciekawy z dwóch powodów. Po pierwsze akceptuje słowo puste. Możemy spróbować podać automatowi słowo puste, a automat je zaakceptuje, jeśli stan początkowy jest jednocześnie stanem akceptującym – a w tym automacie tak właśnie jest. Ponieważ słowo puste nie zawiera dwóch zer pod rząd, jest to poprawne. Druga ciekawostka: w tym automacie wszystkie stany są akceptujące. Automat nie zaakceptuje słowa jedynie wtedy, gdy ze stanu nie będzie wychodzić żadne przejście. Dzieje się tak w stanie q₁, który nie ma przejścia dla 0, bo wtedy słowo zawierałoby dwa zera pod rząd.

4. Zbuduj automat nad alfabetem {-,+,.,0,1,…,9}, który akceptuje tylko słowa przedstawiające liczbę. Czyli albo liczbę całkowitą, jak np. 2, 548, 98263, albo ułamek dziesiętny, jak np. 5584.48, 3.14 (z kropką dziesiętną, tak jak w językach programowania), i jedno, i drugie także w wersji ujemnej ze znakiem minus -2, -548, -3.14 oraz z jawnie zapisanym plusem, czyli +2, +548, +3.14. Jednocześnie musimy umieć zapisać liczbę 0.123 jako samo .123 (bez zera na początku), i to łącznie z oboma znakami. Wprowadzimy pomocnicze oznaczenie: zamiast wypisywać dziesięć przejść dla dziesięciu cyfr, będziemy używać symbolu N.

   

5. Zbuduj automat nad alfabetem binarnym, który akceptuje tylko słowa postaci 0ⁿ1ⁿ, co oznacza, że słowa mają na początku pewną liczbę zer, po których następuje tyle samo jedynek. Przykładami takich słów są 0011, 00001111, 01.

   Takiego automatu nie da się zbudować, bo nigdzie nie potrafimy „zapamiętać” liczby zer. Musielibyśmy utworzyć kilka „podautomatów”, podobnie jak w drugim przykładzie, tyle że tych „podautomatów” musiałoby być nieskończenie wiele, po jednym dla każdej wartości n.

Formalny opis obliczenia automatu

Formalnie zdefiniowaliśmy już sam automat skończony. Musimy jeszcze zdefiniować, co taki automat właściwie robi, czyli zdefiniujemy obliczenie automatu.

Konfiguracja automatu: powiemy, że para $\left<q, w\right> \in Q \times \Sigma^\ast$ jest konfiguracją automatu, gdzie q jest aktualnym stanem, w którym automat się znajduje, a w jest jeszcze nieprzeczytaną częścią słowa. $\Sigma^\ast$ oznacza domknięcie alfabetu $\Sigma$, czyli zbiór wszystkich słów, które da się złożyć z liter alfabetu $\Sigma$. Do domknięcia należy też słowo puste, które oznaczamy $\varepsilon$.

Jeśli mamy automat $\left<Q, \Sigma, \delta, q_0, F\right>$ i próbujemy zaakceptować słowo w, to automat znajduje się w konfiguracji początkowej <q₀, w>. Jeśli wrócimy do automatu

i będziemy chcieli zaakceptować słowo w = abbc, to konfiguracją początkową będzie <q₀, abbc>.

Krok obliczenia definiujemy jako relację $\mapsto$ będącą podzbiorem $(Q\times\Sigma^\ast)\times(Q\times\Sigma^\ast)$, czyli między konfiguracjami automatu. Niech w = w₀w₁… w_n oznacza jeszcze nieprzeczytaną część słowa w. Wtedy powiemy, że pary <q₁, w₀w₁… w_n> i <q₂, w₁… w_n> są w relacji $\mapsto$, co zapisujemy jako

$$ \left<q_1, w_0w_1\dots w_n\right> \mapsto \left<q_2, w_1\dots w_n\right>, $$

wtedy i tylko wtedy, gdy δ(q₁, w₀) = q₂. Wracając do naszego przykładu: konfiguracja początkowa to <q₀, abbc>. Z diagramu widzimy, że dla wejścia „a” możemy przejść do stanu q₁. Możemy więc napisać

$$ \left<q_0, abbc\right> \mapsto \left<q_1, bbc\right>, $$

bo zachodzi δ(q₀, a) = q₁. Tym samym wykonaliśmy jeden krok obliczenia – sprawdziliśmy, do jakiego stanu powinniśmy przejść dla danego wejścia (= pierwszej litery jeszcze nieprzeczytanej części słowa), przeszliśmy tam i usunęliśmy z nieprzeczytanej części słowa pierwszą literę. W ten sposób otrzymaliśmy nową konfigurację.

Domknięcie zwrotne i przechodnie relacji kroku obliczenia oznaczamy $\mapsto^\ast$. Jeśli więc napiszemy $K_1 \mapsto^\ast K_2$, gdzie K₁, K₂ są konfiguracjami automatu, oznacza to, że z konfiguracji K₁ potrafimy w kilku krokach obliczenia dostać się do konfiguracji K₂, innymi słowy istnieje skończony ciąg konfiguracji taki, że:

$$ K_1 \mapsto K_{11} \mapsto K_{12} \mapsto K_{13} \mapsto \dots \mapsto K_2 $$

Na przykład w naszym automacie zachodzi $\left<q_0, abbc\right> \mapsto^\ast \left<q_1,bc\right>$, bo gdy wykonamy dwa kroki obliczenia, zostanie nam słowo „bc” i zostaniemy w stanie q₁. Czyli istnieje taki ciąg konfiguracji:

$$ \left<q_0, abbc\right> \mapsto \left<q_1, bbc\right> \mapsto \left<q_1,bc\right> $$

Automat akceptuje słowo w wtedy i tylko wtedy, gdy istnieje q_f ∈ F taki, że $$\left<q_0, w\right> \mapsto^\ast \left<q_f, \varepsilon\right>$$ Oznacza to, że automat akceptuje słowo w wtedy i tylko wtedy, gdy istnieje jakiś ciąg kroków obliczenia taki, że na jego końcu przeczytaliśmy całe słowo i znajdujemy się w stanie akceptującym automatu. To, że przeczytaliśmy całe słowo, wyraża fakt, że w konfiguracji na miejscu słowa stoi $\varepsilon$, czyli słowo puste. Nasz automat akceptuje słowo abbc, bo istnieje taki ciąg konfiguracji:

$$ \left<q_0, abbc\right> \mapsto \left<q_1, bbc\right> \mapsto \left<q_1,bc\right> \mapsto \left<q_1, c\right> \mapsto \left<q_2, \varepsilon\right> $$

a stan q₂ jest stanem akceptującym, q₂ ∈ F.

Język akceptowany przez automat to zbiór wszystkich słów, które automat akceptuje. Język automatu A będziemy oznaczać L(A). Zachodzi więc $L(A) \subseteq \Sigma^\ast$ oraz

$$ L(A) = \left\{w \in \Sigma^\ast,|,A \mbox{ akceptuje słowo } w\right\} $$

Język regularny to taki język, który jest akceptowany przez jakiś automat skończony.

Dwa automaty skończone są równoważne, jeśli akceptują ten sam język. Czyli automaty A₁ i A₂ są równoważne, jeśli zachodzi L(A₁) = L(A₂).

Źródła

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools