Automat skończony

Z Wikipedii

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.

[edytuj] 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₁ , i po przeczytaniu każdej cyfry (bitu) przechodzi do stanu S_j (gdzie: j=1 lub 2)

stan startowy - S₁

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₁(q₀) automat z diagramu akceptuje każdy ciąg z parzystą liczbą 0 (w tym ciąg bez 0 oraz ciąg pusty ε)

[edytuj] 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₀, i po przeczytaniu każdej cyfry przechodzi do stanu S_j (gdzie: j=0, 1 lub 2)

stan startowy - S₀

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

	0	1
S0	S0	S1
S1	S2	S0
S2	S1	S2

[edytuj] Patrz także

• Automat Moore'a
• Automat Mealy'ego
• Deterministyczny automat skończony
• Niedeterministyczny automat skończony

To jest tylko zalążek artykułu związanego z matematyką. Jeśli potrafisz, rozbuduj go.