Podręcznik

Automaty skończone są abstrakcyjnymi modelami rzeczywistych systemów cyfrowych.

Automat skończony lub dokładniej deterministyczny automat skończony (DAS) to piątka uporządkowana $(Q, \Sigma, \delta, q_0, F)$, gdzie $Q$ - jest zbiorem stanów, $\Sigma$ - alfabetem wejściowym, $\delta:Q\times\Sigma\rightarrow Q$ - funkcją przejść automatu, $q_0\in F$ - tzw. stanem początkowym a $F$ – zbiorem stanów końcowych.

Stan automatu umożliwia pamiętanie historii wejścia tzn. stan w chwili bieżącej. Ogólnie rzecz biorąc zależy od słowa podanego na wejście w chwilach poprzednich.

Mówimy, że automat skończony akceptuje słowo pojawiające się na wejściu automatu, jeśli ciąg przejść ze stanu do stanu odpowiadający literom słowa wejściowego prowadzi od stanu początkowego $q_0$ do jakiegoś stanu $q$ akceptowalnego tzn takiego że $q\in F$.

Automat skończony wyobrażamy sobie jako układ o skończonej liczbie stanów, z jednym wejściem, który znajduje się w pewnym stanie $q$ i czyta ciąg symboli z alfabetu $\Sigma$, czyli czyta słowo nad alfabetem $\Sigma$ podane na wejście. Układ działa w dyskretnych chwilach, które dla uproszczenia utożsamiamy z liczbami naturalnymi. W każdej chwili $n\in N$ automat może odczytać tylko jedną literę słowa $a_n \in \Sigma$ czyta ją i zmienia stan ze stanu $q_{n-1}$ zgodnie z funkcją przejścia na $\tilde{\delta}(q_{n-1},a_n)=q_n$ po czym automat staje i czeka na następną chwilę. W kolejnych chwilach pojawiają się więc na wejściu litery $a_1,a_2,...,a_n\in\Sigma$ i następują zmiany stanu. Jeśli $\tilde{\delta}(q_{n-1},a_n)=q_n\in F$ tzn. dotarliśmy do stanu akceptującego to uważamy, że automat zaakceptował słowo wejściowe $a_1a_2...a_n$ dotychczas podane na wejście automatu.

Jeśli mamy funkcję przejścia $\delta:\Sigma\times Q\rightarrow Q$ to w naturalny sposób można ją rozszerzyć do funkcji $a\in\Sigma$ definiując $\tilde{\delta}$ następująco:

• $\tilde{\delta}(q,\varepsilon)=q$ dla każdego $q\in Q$
• $\tilde{\delta}(q,wa)=\delta(\tilde{\delta}(q,w),a)$ dla każdego $q\in Q$, dla każdego $a\in\Sigma$ i dla każdego słowa $w$ nad alfabetem $\Sigma$

Język akceptowany przez automat skończony $M=(Q,\Sigma,S,\delta,q_0,F)$ to z definicji zbiór $L(M)\overset{df}{=} \{x\in\Sigma^*; \tilde{\delta}(q_0,x)\in F\}\subseteq\Sigma^*$. Język $L\subseteq\Sigma^*$ nazywamy językiem regularnym, jeśli jest akceptowany przez jakiś automat skończony $M=(Q,\Sigma,S,\delta,q_0,F)$

Niedeterministyczny automat skończony to piątka uporządkowana $(Q,\Sigma,\delta,q_0,F)$, gdzie $Q$ jest zbiorem stanów automatu, $\Sigma$ alfabetem wejściowym, $q_0\in F$ - tzw. stanem początkowym, $F$ - zbiorem stanów końcowych a $\tilde{\delta}:Q\times\Sigma\rightarrow 2^Q$ - funkcją przejść automatu niedeterministycznego. Przypominamy, że symbolem $2^Q$ oznaczamy zbiór wszystkich podzbiorów zbioru $Q$.

Zbiór $\delta:(q,a)\subseteq Q$ jest zbiorem wszystkich stanów do których możliwe jest przejście ze stanu $q$ pod wpływem litery $a$ podanej na wejście automatu.

Zauważmy, że zdefiniowane wyżej automaty są automatami bez wyjścia. Ponieważ w praktyce najczęściej mamy do czynienia z systemami cyfrowymi z wyjściem, dlatego też wprowadza się definicje automatów skończonych z wyjściem.

Automat skończony z wyjściem to szóstka uporządkowana $(Q,\Sigma,Y,\delta,\lambda,q_0)$, gdzie $Q, \Sigma, Y$ są alfabetami, $\delta$ i $\lambda$ są funkcjami oraz $q_0\in S$. $\Sigma$ to alfabet wejściowy, $Y$ alfabet wyjściowy a $Q$ jest tzw. zbiorem stanów. Funkcja $\delta:Q\times\Sigma\rightarrow Q$ nosi nazwę funkcji przejść, funkcja $\lambda:Q\rightarrow Y$ nazywa się funkcją wyjść, a $q_0\in S$ jest tzw. stanem początkowym. Tak zdefiniowany automat nazywa się automatem Moore’a.

Jeśli funkcja $\lambda$ jest funkcją bezpośrednio zależną od wejścia tzn. $\lambda:Q\times\Sigma\rightarrow Y$, to taką szóstkę uporządkowaną $(X,Y,S,\delta,\lambda,q_0)$ nazywamy automatem Mealy'ego.

Automat skończony z wyjściem wyobrażamy sobie jako układ o skończonej liczbie stanów, z jednym wejściem i jednym wyjściem, który znajduje się w pewnym stanie $q$ i czyta ciąg symboli $a_1a_2...a_n$ z alfabetu $\Sigma$ czyli czyta słowo nad alfabetem $\Sigma$ podane na wejście. Układ działa w dyskretnych chwilach, które dla uproszczenia utożsamiamy z liczbami naturalnymi 1,2,3..... W każdej chwili $n\in N$ automat może odczytać tylko jedną literę słowa $a_n\in\Sigma$ czyta ją i zmienia stan ze stanu $q_{n-1}$ zgodnie z funkcją przejścia na $\tilde{\delta}(q_{n-1},a_n)=q_n$ i wyprowadza na wyjście literę $\lambda(q_n)$ w przypadku automatu Moore’a lub $\lambda(q_n,a_n)=b_n$ w przypadku automatu Mealy’ego po czym automat staje i czeka na następną chwilę. W kolejnych chwilach pojawiają się więc na wejściu litery $a_1,a_2,...,a_n\in\Sigma$, na wyjściu litery $b_1,b_2,...,b_n\in Y$ i następują zmiany stanu. Automaty Moore’a i Mealy’ego są więc urządzeniami do przetwarzania słów.

Układ sekwencyjny to układ elektroniczny realizujący automat skończony.

Rys. 2. Przetwarzanie słów przez automat skończony bez wyjścia

Rys. 3. Przetwarzanie słów przez automat skończony z wyjściem

Rys. 4. Schemat blokowy układu automat skończony z wyjściem a) automat Moore’a, b) automat Mealy’ego

Rys. 5. Struktura uniwersalna automatu Moore’a z kodowaniem binarnym symboli wejściowych, wyjściowych i stanów; rejestr stanu jest rejestrem r bitowym

Rys. 6. Struktura uniwersalna automatu Mealy’ego z kodowaniem binarnym symboli wejściowych, wyjściowych i stanów

Opis automatu grafem. Z każdym automatem skończonym wiążemy diagram przejść lub dokładniej graf automatu. Jest to graf skierowany w którym wierzchołki grafu odpowiadają stanom automatu Jeśli w automacie istnieje przejście ze stanu $q_1\in Q$ do stanu $q_2\in Q$ przy wejściu $a\in\Sigma$ to diagram zawiera gałąź prowadzącą ze stanu $q_1\in Q$ do stanu $q_2\in Q$ i opatrzoną etykietą $a\in\Sigma$.

Rys.7. Opis automatu grafem. Z każdym automatem skończonym wiążemy diagram przejść czyli graf skierowany opisujący działanie automatu