finite automaton can be classified into two types −

• deterministic finite automaton (dfa)
• non-deterministic finite automaton (ndfa / nfa)

deterministic finite automaton (dfa)

in dfa, for each input symbol, one can determine the state to which the machine will move. hence, it is called deterministic automaton. as it has a finite number of states, the machine is called deterministic finite machine or deterministic finite automaton.

formal definition of a dfa

a dfa can be represented by a 5-tuple (q, ∑, δ, q₀, f) where −

• q is a finite set of states.

• ∑ is a finite set of symbols called the alphabet.

• δ is the transition function where δ: q × ∑ → q

• q₀ is the initial state from where any input is processed (q₀ ∈ q).

• f is a set of final state/states of q (f ⊆ q).

graphical representation of a dfa

a dfa is represented by digraphs called state diagram.

• the vertices represent the states.
• the arcs labeled with an input alphabet show the transitions.
• the initial state is denoted by an empty single incoming arc.
• the final state is indicated by double circles.

example

let a deterministic finite automaton be →

• q = {a, b, c},
• ∑ = {0, 1},
• q₀ = {a},
• f = {c}, and

transition function δ as shown by the following table −

its graphical representation would be as follows −