Niedeterministyczny automat skończony: Różnice pomiędzy wersjami
[wersja przejrzana] | [wersja przejrzana] |
m robot poprawia: en:Nondeterministic finite-state machine |
m robot poprawia: es:Autómata finito no determinista |
||
Linia 25: | Linia 25: | ||
[[el:Μη ντετερμινιστικό πεπερασμένο αυτόματο]] |
[[el:Μη ντετερμινιστικό πεπερασμένο αυτόματο]] |
||
[[en:Nondeterministic finite-state machine]] |
[[en:Nondeterministic finite-state machine]] |
||
[[es:Autómata finito |
[[es:Autómata finito no determinista]] |
||
[[fa:اتوماتون تعینناپذیر متناهی]] |
[[fa:اتوماتون تعینناپذیر متناهی]] |
||
[[hr:Nedeterministički konačni automat]] |
[[hr:Nedeterministički konačni automat]] |
Wersja z 23:51, 31 mar 2010
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.