Niedeterministyczny automat skończony: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
m robot dodaje: fa:اتوماتون تعینناپذیر متناهی |
drobne redakcyjne |
||
Linia 1:
'''Niedeterministyczny automat skończony''' ([[język angielski|ang.]] ''Non-deterministic Finite-state Automaton'', '''NFA''')
== 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
== 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
Linia 12 ⟶ 16:
P(S) jest [[zbiór potęgowy|zbiorem potęgowym]] zbioru stanów S.
▲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]]
| |||