Deterministic Finite Automata (DFA)

Definition: A DFA is 5-tuple or quintuple M = (Q, Σ, δ, q₀, A) where

Q is non-empty, finite set of states.

Σ is non-empty, finite set of input alphabets.

δ is transition function, which is a mapping from Q x Σ to Q.

q₀ ∈ Q is the start state.

A ⊆ Q is set of accepting or final states.

Note: For each input symbol a, from a given state there is exactly one transition (there can be no transitions from a state also) and we are sure (or can determine) to which state the machine enters. So, the machine is called Deterministic machine. Since it has finite number of states the machine is called Deterministic finite machine or Deterministic Finite Automaton or Finite State Machine (FSM).

The language accepted by DFA is

L(M) = { w | w ∈ Σ* and δ*(q₀, w) ∈ A }

The non-acceptance of the string w by an FA or DFA can be defined in formal notation as:

L(M) = { w | w ∈ Σ* and δ*(q₀, w) ∉ A }