Niedeterministyczny automat skończony: Różnice pomiędzy wersjami

drobne redakcyjne
(drobne redakcyjne)
'''Niedeterministyczny automat skończony''' ([[język angielski|ang.]] ''Non-deterministic Finite-state Automaton'', '''NFA''') to- [[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 [[deterministyczny automat skończony|deterministycznego automatu skończonego]] tym, że przeczytanie 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 [[determinizacja automatu skończonego|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
P(S) jest [[zbiór potęgowy|zbiorem potęgowym]] zbioru stanów S.
 
=== Zobacz też ===
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 [[determinizacja automatu skończonego|determinizacji automatu skończonego]].
 
=== Zobacz też ===
* [[Automat Büchiego]]
 
46 439

edycji