Deterministic Finite Acceptor (DFA):


A DFA is defined by the quintuple M = (Q, ∑ , δ,  q0, F)

Q  is a finite set of initial states.

is a finite set of symbols called the input alphabet.

q0  Q is the initial state

F ⊆ Q  is the set of final states

δ: Q X ∑ → Q  is a total functions called transition function.

λ move is not allowed at DFA. This transition not allowed λ move.


Language accepted by DFA (M) is the set of all strings on ∑ accepted by M.

  • ∀ω ∊ L, δ*(q0, ω) ∊ F (string ω accepted)
  • ∀ω ∉ L, δ*(q0, ω) ∉ F ( string ω rejected)