Deterministyczny automat skończony
Automat skończony można podzielić na dwa typy -
- Deterministyczny automat skończony (DFA)
- Niedeterministyczny automat skończony (NDFA / NFA)
Deterministyczny automat skończony (DFA)
W DFA dla każdego symbolu wejściowego można określić stan, do którego maszyna się przejdzie. Stąd to się nazywaDeterministic Automaton. Ponieważ ma skończoną liczbę stanów, nazywana jest maszynąDeterministic Finite Machine lub Deterministic Finite Automaton.
Formalna definicja DFA
DFA można przedstawić jako 5-krotkę (Q, ∑, δ, q 0 , F), gdzie -
Q jest skończonym zbiorem stanów.
∑ jest skończonym zbiorem symboli zwanym alfabetem.
δ jest funkcją przejścia, gdzie δ: Q × ∑ → 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 DFA
DFA jest reprezentowane przez digrafy zwane state diagram.
- 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.
Przykład
Niech deterministyczny automat skończony będzie →
- Q = {a, b, c},
- ∑ = {0, 1},
- q 0 = {a},
- F = {c} i
Funkcja przejścia δ, jak pokazano w poniższej tabeli -
| Stan obecny | Następny stan dla wejścia 0 | Następny stan dla wejścia 1 |
|---|---|---|
| a | za | b |
| b | do | za |
| c | b | do |
Jej reprezentacja graficzna wyglądałaby następująco -
