✖

Automat skończony

Kapitoly: Automat skończony, Automat całkowity, Niedeterministyczny automat skończony, Symulacja NKA, Konwersja NKA na DKA

Automat skończony (angielski: finite state machine lub finite automaton) to model obliczeniowy prymitywnego komputera, który składa się z kilku stanów i kilku przejść, i który może zaakceptować lub odrzucić przekazane słowo.

Przykład

Nieformalnie opisujemy automat skończony za pomocą diagramu stanów, który opisuje automat skończony:

Przykład prostego automatu skończonego

Automat składa się ze stanów, na rysunku są trzy okrągłe stany q0, q1 i q2. Pomiędzy tymi stanami są przejścia, są to strzałki. Ponadto w automacie musi istnieć stan początkowy, czyli stan q0. Stan początkowy jest często przedstawiany poprzez wskazanie strzałki, która nie pochodzi z żadnego stanu. Następnie w automacie zwykle występuje stan końcowy, który jest pokazany podwójną linią, więc na obrazku jest to stan q2.

Automat skonstruowany w ten sposób otrzymuje pewne słowa. Umieszczamy więc jakieś słowa w automacie, a automat próbuje je zaakceptować. Jeśli je zaakceptuje, odpowie TAK, jeśli ich nie zaakceptuje, odpowie NIE. Nasz automat próbuje zaakceptować słowa składające się z liter "a, b, c", więc możemy spróbować zaakceptować słowo "abbc".

Zaczynamy w stanie początkowym q0, a wejściem jest słowo "abbc". Następnie podążamy za klawiszami strzałek.

Przejdziemy przez słowo klasycznie od lewej do prawej, czyli najpierw weźmiemy symbol "a". Strzałka dla wejścia "a" prowadzi do stanu q1, więc przechodzimy tam i usuwamy symbol "a" ze słowa. Na wejściu mamy słowo "bbc":

Strzałka dla wejścia "b" wraca do węzła q1. Ponownie usuwamy pierwszą literę i mamy słowo "bc" jako dane wejściowe. Ponownie pozostajemy w stanie q1. Wreszcie, na wejściu mamy słowo "c". Ze stanu q1 strzałka dla wejścia "c" wysyła nas do stanu q2.

Zużyliśmy już wszystkie litery ze słowa wejściowego i znajdujemy się w stanie q2, który jest stanem końcowym. Ten automat skończony akceptuje więc słowo "abbc".

Gdybyśmy na końcu nie znajdowali się w stanie odbioru, automat nie zaakceptowałby tego słowa. Podobnie, automat nie zaakceptowałby słowa, gdybyśmy znajdowali się w stanie, w którym nie ma dokąd pójść. Na przykład, aby wprowadzić "ab", musielibyśmy być w stanie q1 i tam byśmy skończyli - automat nie zaakceptowałby tego słowa. Gdybyśmy przetestowali słowo "aabbc", znów nie mielibyśmy szczęścia, ponieważ nie ma strzałki prowadzącej ze stanu q1 dla litery "a".

Końcowy automat jest więc używany do rozpoznawania pewnego zestawu słów. W praktyce moglibyśmy użyć automatu na przykład do określenia, czy dane słowo wejściowe jest prawidłowym e-mailem.

Definicja skończonego automatu

Musimy sformalizować poprzednie intuicyjne pojęcie tego, czym jest automat skończony, aby móc dalej i lepiej pracować z automatami.

Powiemy, że automat skończony (deterministyczny) jest kwintylem $\left<Q, \Sigma, \delta, q_0, F\right>$, gdzie

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

Wracając do poprzedniego automatu,

możemy powiedzieć, że istnieją trzy stany w zbiorze stanów Q Q = {q0, q1, q2} . Alfabet $\Sigma$ zawiera litery, z których możemy tworzyć słowa, które automat następnie zaakceptuje lub odrzuci. W tym przypadku prawdopodobnie będzie to alfabet $\Sigma=\left\{a, b, c\right\}$, ale może to być dowolny superzbiór. Początkowym stanem q0 jest stan q0, nic tego nie zmienia. Zbiór stanów końcowych ma tylko jeden stan w tym automacie F = {q2}.

Funkcja przejścia to trzy strzałki z literami. Jeśli jesteś zdezorientowany oznaczeniem $\delta: Q \times \Sigma\longrightarrow Q$, oznacza to po prostu, że δ jest funkcją (może lepiej widokiem), która przyjmuje dwa parametry: stan z Q i literę z $\Sigma$. Kiedy funkcja jest wywoływana, zwraca nowy stan. Moglibyśmy zdefiniować naszą funkcję przejścia za pomocą tabeli w następujący sposób:

$$ \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 δ(q1, c), zastosujemy trzecią linię, a funkcja odpowie stanem q2 - tak jak na diagramie. Jeśli jesteśmy w stanie q1 i wejściem jest litera "c", otrzymamy stan q2. Zanim formalnie zdefiniujemy, co to znaczy, że automat akceptuje słowo, użyjmy naszego intuicyjnego zrozumienia tej koncepcji, aby pokazać więcej przykładów.

Inne przykłady

  1. Utwórz automat, który operuje na alfabecie binarnym, tj. $\Sigma=\left\{0,1\right\}$, i akceptuje tylko słowa kończące się na jeden. Na przykład, akceptuje on słowa 1, 01, 000001, 0101011.

    Nasz automat ma dwa stany - początkowy q0 i końcowy q1. Za każdym razem, gdy mamy cyfrę 1 jako dane wejściowe, przechodzimy do stanu końcowego q1 i pozostajemy w nim. I odwrotnie, jeśli wejściem jest cyfra 0, przechodzimy do stanu niekońcowego q0 i również w nim pozostajemy.

  2. Skonstruuj automat nad alfabetem binarnym, który akceptuje tylko słowa, których litera początkowa różni się od litery końcowej.

    Automat dzieli się na dwa "pod-automaty" już w pierwszym kroku. Jeśli słowo zaczyna się od zera, automat wchodzi do lewej części i tam pozostaje, jeśli zaczyna się od jedynki, przenosi się do prawej części. Potem jest klasycznie, jeśli jesteśmy w lewej części i na wejściu jest 1, to przechodzi do stanu końcowego i już tam zostaje. Jeśli na wejściu jest 0, przechodzimy do stanu q1, który nie jest stanem końcowym.

    W przeciwieństwie do poprzednich automatów, ten automat ma wiele stanów końcowych, tj. F = {q3, q4}.

  3. Skonstruuj automat w alfabecie binarnym, który akceptuje tylko słowa niezawierające dwóch kolejnych zer.

    Automat ten jest interesujący z dwóch powodów: po pierwsze, akceptuje on puste słowa. Możemy spróbować umieścić puste słowo w automacie, a automat zaakceptuje je, jeśli stan początkowy jest również stanem końcowym, co właśnie miało miejsce w przypadku tego automatu. Ponieważ puste słowo to słowo, które nie zawiera dwóch zer w rzędzie, jest to właściwe rozwiązanie. Inną interesującą rzeczą jest to, że ten automat ma wszystkie stany końcowe. Tak więc jedynym przypadkiem, w którym automat nie zaakceptowałby słowa, jest brak przejścia ze stanu. Dzieje się tak w stanie q1, który nie ma przejścia dla 0, ponieważ wtedy słowo zawierałoby dwa zera pod rząd.

  4. Skonstruuj automat nad alfabetem {-,+,...,0,1,...,9}, który akceptuje tylko słowa reprezentujące liczbę. To znaczy, albo liczbę całkowitą, taką jak 2, 548, 98263, albo dziesiętną, taką jak 5584.48, 3.14, i obie z wersją dla liczby ujemnej ze znakiem minus -2, -548, -3.14, a także z wyraźnym znakiem plus, tj. +2, +548, +3.14. Jednocześnie musimy być w stanie zapisać liczbę 0.123 jako .123 (bez wiodącego zera) i z uwzględnieniem obu znaków. Wprowadzimy notację, w której zamiast zapisywać dziesięć przejść dla dziesięciu cyfr, użyjemy symbolu N.

  5. Skonstruuj automat nad alfabetem binarnym, który będzie akceptował tylko słowa o postaci 0n1n, co oznacza, że słowa mają określoną liczbę zer na początku, po których następuje taka sama liczba jedynek. Przykładami takich słów są 0011, 00001111, 01.

    Nie możemy zbudować takiego automatu, ponieważ nie jesteśmy w stanie "zapamiętać" liczby zer w dowolnym miejscu. Musielibyśmy stworzyć kilka "podautomatów", jak w drugim przykładzie, ale tych "podautomatów" musiałoby być nieskończenie wiele, po jednym dla każdej wartości n.

Formalizacja obliczeń automatu

Zdefiniowaliśmy już formalnie sam automat skończony. Następnie musimy jeszcze zdefiniować, co taki automat faktycznie robi, tj. zdefiniować obliczenia automatu.

Konfiguracja automatu: Mówimy, że para $\left<q, w\right> \in Q \times \Sigma^\ast$ jest konfiguracją automatu, gdzie q jest aktualnym stanem automatu, a w jest nieprzeczytaną częścią słowa. $\Sigma^\ast$ oznacza domknięcie alfabetu $\Sigma$, czyli zbiór wszystkich słów, które można ułożyć z liter alfabetu $\Sigma$. Domknięcie zawiera słowo puste, które oznaczamy przez $\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 <q0, w>. Jeśli wrócimy do automatu

i spróbujemy zaakceptować słowo w = abbc, wówczas początkowa konfiguracja to <q0, abbc>.

Krok obliczeniowy definiujemy jako relację $\mapsto$ między zbiorami $(Q\times\Sigma^\ast)\times(Q\times\Sigma^\ast)$, tj. między konfiguracjami automatu. Niech w = w0w1… wn reprezentuje nieprzeczytaną część słowa w. Wtedy mówimy, że pary <q1, w0w1… wn> i <q2, w1… wn> są w sesji $\mapsto$, zapisanej jako

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

tylko jeśli δ(q1, w0) = q2. Wracając do naszego przykładu, początkowa konfiguracja to <q0, abbc>. Z diagramu widzimy, że dla wejścia "a" możemy przejść do stanu q1. Możemy więc napisać

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

ponieważ δ(q0, a) = q1 ma zastosowanie. W ten sposób wykonaliśmy jeden krok obliczeń - sprawdziliśmy, do jakiego stanu powinniśmy przejść dla danego wejścia (= pierwsza litera nieprzeczytanej części słowa), przenieśliśmy się tam i usunęliśmy pierwszą literę z nieprzeczytanej części słowa. To dało nam nową konfigurację.

Refleksyjne i przechodnie domknięcie sesyjnego kroku obliczeń oznaczamy przez $\mapsto^\ast$. Jeśli więc napiszemy $K_1 \mapsto^\ast K_2$, gdzie K1, K2 są konfiguracjami automatu, oznacza to, że możemy przejść od konfiguracji K1 do konfiguracji K2, lub istnieje skończona sekwencja konfiguracji takich, że:

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

Na przykład w naszym automacie $\left<q_0, abbc\right> \mapsto^\ast \left<q_1,bc\right>$, ponieważ jeśli wykonamy dwa kroki obliczeń, to zostaniemy ze słowem "bc" i pozostaniemy w stanie q1. Oznacza to, że istnieje taka sekwencja 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 taki qf ∈ F, że $$\left<q_0, w\right> \mapsto^\ast \left<q_f, \varepsilon\right>$$ Czyli automat akceptuje słowo w wtedy i tylko wtedy, gdy istnieje taka sekwencja kroków obliczeniowych, że na końcu tej sekwencji przeczytaliśmy całe słowo i jesteśmy w stanie końcowym automatu. To, że przeczytaliśmy całe słowo wyraża fakt, że znajduje się ono w konfiguracji zamiast słowa $\varepsilon$, które jest słowem pustym. Nasz automat akceptuje słowo abbc, ponieważ istnieje taka sekwencja 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 q2 jest stanem końcowym, q2 ∈ F.

Językakceptowany przez automat to zbiór wszystkich akceptowanych przez niego słów. Będziemy oznaczać język automatu A jako L(A). Zatem, $L(A) \subseteq \Sigma^\ast$ i

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

Język regularny to język akceptowany przez pewien automat skończony.

Dwa skończone automaty są równoważne, jeśli akceptują ten sam język. Oznacza to, że automaty A1 i A2 są równoważne, jeśli zachodzi L(A1) = L(A2).

Źródła