Automat skończony

Przykład automatu skończonego

Automat skończony (ang. finite state machine, FSM) – abstrakcyjny, matematyczny, iteracyjny model zachowania systemu dynamicznego oparty na tablicy dyskretnych przejść między jego kolejnymi stanami (diagram stanów).

Ze względu na charakter przejść między stanami, wyróżnia się deterministyczne i niedeterministyczne automaty skończone.

Automaty skończone są ważnym narzędziem teoretycznym w tworzeniu i testowaniu oprogramowania, a jako modele szerszych procesów znajdują także swoje zastosowanie w matematyce i logice, lingwistyce, filozofii, czy biologii.

Maszyna Turinga jest generalizacją automatu skończonego operującą na nieskończonej pamięci.

Przykład działania

Na ilustracji po prawej stronie przedstawiono prosty automat skończony, który zachowuje się w sposób stabilny gdy na wejściu otrzymuje wartość binarną 1, i zmienia stan przy napotkaniu 0. Zaczyna on pracę od stanu $S_1$, i po przeczytaniu każdej cyfry (bitu) przechodzi do stanu $S_j$ (gdzie: j=1 lub 2)

stan startowy – $S_1$

$S_1 \rightarrow^1 S_1$

$S_1 \rightarrow^0 S_2$

$S_2 \rightarrow^1 S_2$

$S_2 \rightarrow^0 S_1$

Proces ten można także zapisać w postaci tabeli:

	0	1
S1	S2	S1
S2	S1	S2

Inaczej: przyjmując jako stan początkowy $S_1 (q_0)$ automat z diagramu akceptuje każdy ciąg z parzystą liczbą 0 (w tym ciąg bez 0 oraz ciąg pusty ε)

Przykład 2

Automat badający podzielność liczby wejściowej przez 3

Przedstawiony jako ilustracja we wstępie do artykułu automat jest w stanie badać podzielność liczby wejściowej przez 3. Automat zaczyna pracę od stanu $S_0$, i po przeczytaniu każdej cyfry przechodzi do stanu $S_j$ (gdzie: j = 0, 1 lub 2)

stan startowy – $S_0$

$S_0 \rightarrow^0 S_0$

$S_0 \rightarrow^1 S_1$

$S_1 \rightarrow^0 S_2$

$S_1 \rightarrow^1 S_0$

$S_2 \rightarrow^0 S_1$

$S_2 \rightarrow^1 S_2$

Proces ten można także zapisać w postaci tabeli:

	0	1
S0	S0	S1
S1	S2	S0
S2	S1	S2

Przykład 3

Automat badający podzielność liczby wejściowej przez 4

Na ilustracji po prawej stronie przedstawiono prosty automat skończony badający podzielność liczby wejściowej przez 4. Automat zaczyna pracę od stanu $S_0$, i po przeczytaniu każdej cyfry przechodzi do stanu $S_j$ (gdzie: j=0, 1 lub 2)

stan startowy – $S_0$

$S_0 \rightarrow^0 S_0$

$S_0 \rightarrow^1 S_1$

$S_1 \rightarrow^0 S_0$

$S_1 \rightarrow^1 S_2$

$S_2 \rightarrow^0 S_1$

$S_2 \rightarrow^1 S_2$

Proces ten można także zapisać w postaci tabeli:

	0	1
S0	S0	S1
S1	S0	S2
S2	S1	S2

Zobacz też

• automat Moore’a
• automat Mealy’ego
• deterministyczny automat skończony
• niedeterministyczny automat skończony

Linki zewnętrzne

• Automat Skończony Implementacja skończonej maszyny stanów w języku C