Automat skończony  Wikipedia, wolna encyklopedia http://pl.wikipedia.org/wiki/Automat_skończony
Automat skończony
Z Wikipedii, wolnej encyklopedii
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).
Przykład automatu skończonego
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.
Spis treści
1 Przykład działania
2 Przykład 2
3 Przykład 3
4 Zobacz też
5 Linki zewnętrzne
Przykład działania
1 z 4 29.05.2011 11:29
Automat skończony  Wikipedia, wolna encyklopedia http://pl.wikipedia.org/wiki/Automat_skończony
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:
0 1
S1 S2 S1
S2 S1 S2
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:
2 z 4 29.05.2011 11:29
Automat skończony  Wikipedia, wolna encyklopedia http://pl.wikipedia.org/wiki/Automat_skończony
0 1
S0 S0 S1
S1 S2 S0
S2 S1 S2
Przykład 3
Na ilustracji po prawej stronie przedstawiono
prosty automat skończony. Automat zaczyna
pracę od stanu S0, i po przeczytaniu każdej
cyfry przechodzi do stanu Sj (gdzie: j=0, 1 lub
2)
Przykład automatu skończonego
stan startowy - S0
Proces ten można także zapisać w postaci tabeli:
0 1
S0 S0 S1
S1 S0 S2
S2 S1 S2
Zobacz też
Automat Moore'a
Automat Mealy'ego
Deterministyczny automat skończony
Niedeterministyczny automat skończony
Linki zewnętrzne
3 z 4 29.05.2011 11:29
Automat skończony  Wikipedia, wolna encyklopedia http://pl.wikipedia.org/wiki/Automat_skończony
Maszyna stanów skończonych (http://toan.pl/?publikacje,27) Implementacja
maszyny stanów skończonych w języku C
y
ródło  http://pl.wikipedia.org/wiki/Automat_sko%C5%84czony
Kategoria: Teoria automatów
Tę stronę ostatnio zmodyfikowano 10:20, 25 maj 2011. Tekst udostępniany
na licencji Creative Commons: uznanie autorstwa, na tych samych
warunkach, z możliwością obowiązywania dodatkowych ograniczeń. Zobacz
szczegółowe informacje o warunkach korzystania.
4 z 4 29.05.2011 11:29