Automat skończony

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
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 automatu skończonego[edytuj | edytuj kod]

DFAexample.svg

Na ilustracji po prawej stronie przedstawiono prosty automat skończony mogący przyjąć jeden z dwóch stanów - S_1 lub S_2. Automat zaczyna pracę od stanu S_1 i zachowuje się w sposób stabilny (nie zmienia stanu) tak długo, jak długo na wejściu otrzymuje liczby 1. Każde napotkane na wejściu 0 zmienia stan układu na przeciwny. Proces ten można przedstawić również za pomocą listy przejść

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

jak i tabeli

0
1
S1 S2 S1
S2 S1 S2

Za pomocą tego automatu możemy badać czy liczność zer w danym ciągu jest parzysta czy też nie. Gdy na wejściu pojawi się nieparzysta liczba zer automat przyjmie stan S_2. W każdym innym wypadku automat przyjmie stan S_1.

Przykład wykonania dla ciągu wejściowego 0011010:

liczba na wejściu
(start)
0
0
1
1
0
1
0
stan automatu
S1
S2
S1
S1
S1
S2
S2
S1

Automat zakończył pracę w stanie S_1 co oznacza parzystą ilość (lub brak) liczb 0 w ciągu wejściowym.

Przykład 2[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]