Niedeterministyczny automat skończony

Ten artykuł od 2022-02 wymaga zweryfikowania podanych informacji.

Należy podać wiarygodne źródła w formie przypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

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 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, Q, A), gdzie:

S jest skończonym zbiorem stanów
∑ jest skończonym zbiorem nazywanym alfabetem
T: S × ∑ → P(S) jest funkcją przejścia
Q jest zbiorem stanów początkowych
A jest zbiorem stanów akceptujących (końcowych)

P(S) jest zbiorem potęgowym zbioru stanów S.

Zobacz też