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 -