Niedeterministyczny automat skończony (NFA)
Niedeterministyczny automat skończony (ang. Non-deterministic Finite-state Automaton, NFA) to maszyna o ograniczonej liczbie stanów, która przetwarza symbole słowa, zaczynając od stanu początkowego. Po przeczytaniu każdego symbolu automat przechodzi do jednego z wielu możliwych stanów, zgodnie z relacją przejścia. Jeśli po przetworzeniu całego słowa automat znajduje się w stanie akceptującym, mówimy, że słowo zostało zaakceptowane.
Różnice między NFA a DFA
Niedeterministyczny automat skończony różni się od deterministycznego automatu skończonego (DFA) tym, że w danym stanie może przechodzić do wielu różnych stanów po odczytaniu tego samego symbolu. Dla każdego NFA istnieje odpowiadający mu DFA, który akceptuje te same słowa. Proces ten nazywa się determinizacją.
Formalny opis NFA
Niedeterministyczny automat skończony można formalnie zdefiniować jako pięciokrotność uporządkowaną (S, ∑, T, Q, A), gdzie:
- S – skończony zbiór stanów
- ∑ – skończony zbiór symboli, nazywany alfabetem
- T: S × ∑ → P(S) – funkcja przejścia, która przypisuje stanom i symbolom zbiór możliwych stanów
- Q – zbiór stanów początkowych
- A – zbiór stanów akceptujących (końcowych)
P(S) oznacza zbiór potęgowy zbioru stanów S.
