Automat skończony

Automat skończony (ang. finite state machine^[1]) – 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.

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

${\displaystyle S_{1}\to ^{1}S_{1}}$

${\displaystyle S_{1}\to ^{0}S_{2}}$

${\displaystyle S_{2}\to ^{1}S_{2}}$

${\displaystyle S_{2}\to ^{0}S_{1},}$

jak i tabeli

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 ${\displaystyle S_{2}.}$ W każdym innym wypadku automat przyjmie stan ${\displaystyle S_{1}.}$

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

Automat zakończył pracę w stanie ${\displaystyle S_{1},}$ co oznacza parzystą liczbę 0 w ciągu wejściowym.

Przedstawiony jako ilustracja we wstępie do artykułu automat jest w stanie badać podzielność liczby wejściowej przez ${\displaystyle 3.}$ Automat zaczyna pracę od stanu ${\displaystyle S_{0},}$ i po przeczytaniu każdej cyfry przechodzi do stanu ${\displaystyle S_{j}}$ (gdzie: ${\displaystyle j=0,1,2}$)

stan startowy – ${\displaystyle S_{0}}$

${\displaystyle S_{0}\to ^{0}S_{0}}$

${\displaystyle S_{0}\to ^{1}S_{1}}$

${\displaystyle S_{1}\to ^{0}S_{2}}$

${\displaystyle S_{1}\to ^{1}S_{0}}$

${\displaystyle S_{2}\to ^{0}S_{1}}$

${\displaystyle S_{2}\to ^{1}S_{2}.}$

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

Na ilustracji po prawej stronie przedstawiono prosty automat skończony badający podzielność liczby wejściowej przez ${\displaystyle 4.}$ Automat zaczyna pracę od stanu ${\displaystyle S_{0},}$ i po przeczytaniu każdej cyfry przechodzi do stanu ${\displaystyle S_{j}}$ (gdzie: ${\displaystyle j=0,1,2}$)

stan startowy – ${\displaystyle S_{0}}$

${\displaystyle S_{0}\to ^{0}S_{0}}$

${\displaystyle S_{0}\to ^{1}S_{1}}$

${\displaystyle S_{1}\to ^{0}S_{2}}$

${\displaystyle S_{1}\to ^{1}S_{1}}$

${\displaystyle S_{2}\to ^{0}S_{0}}$

${\displaystyle S_{2}\to ^{1}S_{1}.}$

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

• automat Büchiego
• automat Moore’a
• automat Mealy’ego
• deterministyczny automat skończony
• niedeterministyczny automat skończony

• Automaton, finite (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-10-05].