Automat skończony - Wikipedia, wolna encyklopedia

Wolna encyklopedia

Przykład automatu skończonego

Automat skończony (ang. finite state machine, FSM) to abstrakcyjny, matematyczny, iteracyjny model zachowania systemu dynamicznego oparty o tablicę 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
S₁	S₂	S₁
S₂	S₁	S₂

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

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 -