Automat skończony

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Przykład automatu skończonego

Automat skończony (ang. finite state machine, FSM) – abstrakcyjny, matematyczny, iteracyjny model obliczeń w teorii automatów oparty na tablicy dyskretnych przejść między jego kolejnymi stanami, do opisu których służy diagram stanów.

Ze względu na charakter przejść między stanami, wyróżnia się deterministyczne i niedeterministyczne automaty skończone. Maszyna Turinga jest generalizacją automatu skończonego operującą na nieskończonej pamięci.

Automaty skończone są wykorzystywane w tworzeniu systemów komputerowych i opisie układów dynamicznych. Zachowania automatów skończonych można zaobserwować w wielu urządzeniach współczesnego społeczeństwa, które wykonują z góry ustaloną sekwencję działań w zależności od sekwencji zdarzeń, z którymi są prezentowane. Najprostszymi przykładami są automaty sprzedające produkty po zdeponowaniu odpowiedniej kombinacji monet, windy, których kolejność postojów jest określona przez piętra wybierane przez pasażerów, sygnalizacja świetlna, która zmienia sekwencję, gdy czekają samochody, oraz zamki szyfrowe, które wymagają wprowadzanie sekwencji liczb we właściwej kolejności.

Przykład automatu skończonego[edytuj | edytuj kod]

DFAexample.svg

Na ilustracji przedstawiono prosty automat skończony mogący przyjąć jeden z dwóch stanów – lub Automat zaczyna pracę od stanu i zachowuje się w sposób stabilny (nie zmienia stanu) tak długo, jak długo na wejściu otrzymuje liczby 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 –

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 W każdym innym wypadku automat przyjmie stan

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 co oznacza parzystą 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 Automat zaczyna pracę od stanu i po przeczytaniu każdej cyfry przechodzi do stanu (gdzie: )

stan startowy –

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 Automat zaczyna pracę od stanu i po przeczytaniu każdej cyfry przechodzi do stanu (gdzie: )

stan startowy –

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

0
1
S0 S0 S1
S1 S2 S1
S2 S0 S1

Zobacz też[edytuj | edytuj kod]