Loading AI tools
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ą relacji 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 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.
Formalnie niedeterministyczny automat skończony można przedstawić jako piątkę uporządkowaną (S, ∑, T, Q, A), gdzie:
P(S) jest zbiorem potęgowym zbioru stanów S.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
