Automat skończony.pdf

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, ﬁlozoﬁi, 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 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:

2 z 4

29.05.2011 11:29

Automat skończony – Wikipedia, wolna encyklopedia

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

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

stan startowy - S 0

Przykład automatu skończonego

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

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

Źródło „http://pl.wikipedia.org/wiki/Automat_sko%C5%84czony”

Kategoria: Teoria automatów

Tę stronę ostatnio zmodyﬁkowano 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

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: