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

_{0}, 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

_{0}∈ 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

_{0}, 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

_{0}, w) ∉ A }
## No comments:

## Post a Comment