Finite State Machines

Prosta implementacja programowa automatów skończonych

Źródła inspiracji

• Automata & Python - Computerphile
• Non-Deterministic Automata - Computerphile

Deterministic finite automaton

Deterministyczny automat skończony reprezentuje piątka: DFA = {Q, Σ, δ, q0, F}, gdzie:

• Q - skończony zbiór stanów automatu
• Σ - skończony zbiór symboli wejściowych (alfabet)
• δ - funkcja przejść (δ: Q × Σ -> Q)
• q0 - stan początkowy (q0 ∈ Q)
• F - zbiór stanów końcowych (F ⊆ Q)

Nondeterministic finite automaton

Niedeterministyczny automat skończony reprezentuje piątka: NFA = {Q, Σ, δ, S, F}, gdzie:

• Q - skończony zbiór stanów automatu
• Σ - skończony zbiór symboli wejściowych (alfabet)
• δ - funkcja przejść (δ: Q × Σ -> P(Q), P - powerset)
• S - zbiór stanów początkowych (S ⊆ Q)
• F - zbiór stanów końcowych (F ⊆ Q)