Niedeterministyczny automat skończony  Wikipedi... http://pl.wikipedia.org/wiki/Niedeterministyczny_a...
Niedeterministyczny automat
skończony
Z Wikipedii, wolnej encyklopedii
Niedeterministyczny automat skończony (ang. Non-deterministic Finite-state
Automaton, NFA) - maszyna o skończonej liczbie stanów, która zaczynając w
stanie początkowym czyta kolejne symbole pewnego słowa. Po przeczytaniu
każdego symbolu zmienia ona swój stan na stan będący elementem zbioru, który
jest wartością funkcji przejścia. Jeśli po przeczytaniu całego słowa maszyna
znajduje się w którymś ze stanów oznaczonych jako akceptujące (końcowe),
mówimy że automat akceptuje czytane słowo.
Niedeterministyczny a deterministyczny automat
skończony
Niedeterministyczny automat skończony różni się od deterministycznego
automatu skończonego tym, że przeczytanie tego samego symbolu w danym
stanie może powodować przejście do jednego z kilku różnych stanów.
Każdemu niedeterministycznemu automatowi skończonemu odpowiada
deterministyczny automat skończony akceptujący dokładnie te same słowa.
Możemy go uzyskać dokonując determinizacji automatu skończonego.
Opis formalny
Formalnie niedeterministyczny automat skończony można przedstawić jako piątkę
uporządkowaną (S, ", T, s, A), gdzie:
S jest skończonym zbiorem stanów
" jest skończonym zbiorem nazywanym alfabetem
T: S � " P(S) jest funkcją przejścia
s jest stanem początkowym
A jest zbiorem stanów akceptujących (końcowych)
P(S) jest zbiorem potęgowym zbioru stanów S.
Zobacz też
Automat B�chiego
1 z 2 29.05.2011 18:00
Niedeterministyczny automat skończony  Wikipedi... http://pl.wikipedia.org/wiki/Niedeterministyczny_a...
y
ródło  http://pl.wikipedia.org/wiki/Niedeterministyczny_automat_sko
%C5%84czony
Kategoria: Teoria automatów
Tę stronę ostatnio zmodyfikowano 22:56, 8 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.
2 z 2 29.05.2011 18:00