Przykład automatu skończonego

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).

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

Automat skończony – Wikipedia, wolna encyklopedia

http://pl.wikipedia.org/wiki/Automat_skończony

1 z 4

29.05.2011 11:29

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 S

1

, i po przeczytaniu

każdej cyfry (bitu) przechodzi do stanu S

j

(gdzie:

j=1 lub 2)

stan startowy - S

1

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

0 1

S

1

S

2

S

1

S

2

S

1

S

2

Inaczej: przyjmując jako stan początkowy S

1

(q

0

) 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 S

0

, i po

przeczytaniu każdej cyfry przechodzi do stanu S

j

(gdzie: j=0, 1 lub 2)

stan startowy - S

0

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

Automat skończony – Wikipedia, wolna encyklopedia

http://pl.wikipedia.org/wiki/Automat_skończony

2 z 4

29.05.2011 11:29

Przykład automatu skończonego

0 1

S

0

S

0

S

1

S

1

S

2

S

0

S

2

S

1

S

2

Przykład 3

Na ilustracji po prawej stronie przedstawiono
prosty automat skończony. 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

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

0 1

S

0

S

0

S

1

S

1

S

0

S

2

S

2

S

1

S

2

Zobacz też

Automat Moore'a
Automat Mealy'ego
Deterministyczny automat skończony
Niedeterministyczny automat skończony

Linki zewnętrzne

Automat skończony – Wikipedia, wolna encyklopedia

http://pl.wikipedia.org/wiki/Automat_skończony

3 z 4

29.05.2011 11:29

Maszyna stanów skończonych (http://toan.pl/?publikacje,27) Implementacja
maszyny stanów skończonych w języku C

Ź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.

Automat skończony – Wikipedia, wolna encyklopedia

http://pl.wikipedia.org/wiki/Automat_skończony

4 z 4

29.05.2011 11:29