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 S1 , i po przeczytaniu każdej cyfry (bitu) przechodzi do stanu Sj (gdzie: j=1 lub 2)
- stan startowy - S1
Proces ten można także zapisać w postaci tabeli:
Inaczej: przyjmując jako stan początkowy S1(q0) 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 S0, i po przeczytaniu każdej cyfry przechodzi do stanu Sj (gdzie: j=0, 1 lub 2)
- stan startowy - S0
Proces ten można także zapisać w postaci tabeli:
| |
0 |
1 |
| S0 |
S0 |
S1 |
| S1 |
S2 |
S0 |
| S2 |
S1 |
S2 |
