Niedeterministyczny automat skończony
W NDFA, dla określonego symbolu wejściowego, maszyna może przejść do dowolnej kombinacji stanów w maszynie. Innymi słowy, nie można określić dokładnego stanu, do którego porusza się maszyna. Stąd to się nazywaNon-deterministic Automaton. Ponieważ ma skończoną liczbę stanów, nazywana jest maszynąNon-deterministic Finite Machine lub Non-deterministic Finite Automaton.
Formalna definicja NDFA
NDFA można przedstawić jako 5-krotkę (Q, ∑, δ, q 0 , F), gdzie -
Q jest skończonym zbiorem stanów.
∑ jest skończonym zbiorem symboli zwanych alfabetami.
δjest funkcją przejścia, gdzie δ: Q × ∑ → 2 Q
(Tutaj pobrano zestaw mocy Q (2 Q ), ponieważ w przypadku NDFA ze stanu może nastąpić przejście do dowolnej kombinacji stanów Q)
q0jest stanem początkowym, z którego przetwarzane jest dowolne wejście (q 0 ∈ Q).
F jest zbiorem stanu / stanów końcowych Q (F ⊆ Q).
Graficzna reprezentacja NDFA: (tak samo jak DFA)
NDFA jest reprezentowane przez digrafy zwane diagramem stanów.
- Wierzchołki reprezentują stany.
- Łuki oznaczone alfabetem wejściowym pokazują przejścia.
- Stan początkowy jest oznaczony pustym pojedynczym łukiem wejściowym.
- Stan końcowy jest oznaczony podwójnymi kółkami.
Example
Niech niedeterministyczny automat skończony będzie →
- Q = {a, b, c}
- ∑ = {0, 1}
- q 0 = {a}
- F = {c}
Funkcja przejścia δ, jak pokazano poniżej -
| Stan obecny | Następny stan dla wejścia 0 | Następny stan dla wejścia 1 |
|---|---|---|
| za | a, b | b |
| b | do | a, c |
| do | pne | do |
Jej reprezentacja graficzna wyglądałaby następująco -
DFA vs NDFA
W poniższej tabeli wymieniono różnice między usługami DFA i NDFA.
| DFA | NDFA |
|---|---|
| Przejście ze stanu następuje do jednego określonego następnego stanu dla każdego symbolu wejściowego. Dlatego nazywa się to deterministycznym . | Przejście ze stanu może następować do wielu następnych stanów dla każdego symbolu wejściowego. Dlatego nazywa się to niedeterministycznym . |
| Puste przejścia ciągów nie są widoczne w DFA. | NDFA zezwala na przejścia pustych ciągów. |
| Wycofywanie jest dozwolone w DFA | W NDFA cofanie się nie zawsze jest możliwe. |
| Wymaga więcej miejsca. | Zajmuje mniej miejsca. |
| Ciąg jest akceptowany przez DFA, jeśli przechodzi do stanu końcowego. | Ciąg jest akceptowany przez NDFA, jeśli przynajmniej jedno ze wszystkich możliwych przejść kończy się w stanie końcowym. |
Akceptory, klasyfikatory i przetworniki
Akceptor (rozpoznający)
Automat obliczający funkcję boolowską nazywa się acceptor. Wszystkie stany akceptora albo akceptują, albo odrzucają dane mu wejściowe.
Klasyfikator
ZA classifier ma więcej niż dwa stany końcowe i daje jedno wyjście po zakończeniu.
Transduktor
Automat, który generuje dane wyjściowe na podstawie bieżącego wejścia i / lub poprzedniego stanu, nazywany jest a transducer. Przetworniki mogą być dwojakiego rodzaju -
Mealy Machine - Wyjście zależy zarówno od aktualnego stanu, jak i aktualnego wejścia.
Moore Machine - Wyjście zależy tylko od aktualnego stanu.
Dopuszczalność przez DFA i NDFA
Ciąg jest akceptowany przez DFA / NDFA, jeśli DFA / NDFA rozpoczynający się w stanie początkowym kończy się stanem akceptacji (dowolnym ze stanów końcowych) po całkowitym przeczytaniu ciągu.
Ciąg S jest akceptowany przez DFA / NDFA (Q, ∑, δ, q 0 , F), iff
δ*(q0, S) ∈ F
Język L akceptowane przez DFA / NDFA
{S | S ∈ ∑* and δ*(q0, S) ∈ F}
Ciąg S ′ nie jest akceptowany przez DFA / NDFA (Q, ∑, δ, q 0 , F), iff
δ*(q0, S′) ∉ F
Językiem L 'nieakceptowanym przez DFA / NDFA (Uzupełnienie akceptowanego języka L) jest
{S | S ∈ ∑* and δ*(q0, S) ∉ F}
Example
Rozważmy DFA pokazane na rysunku 1.3. Z DFA można wyprowadzić dopuszczalne ciągi.
Ciągi akceptowane przez powyższy DFA: {0, 00, 11, 010, 101, ...........}
Ciągi nieakceptowane przez powyższy DFA: {1, 011, 111, ........}