Types Of finite Automata - DFA

Types Of finite Automata

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, Σ, δ, q0, 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
·         q0 is the initial state from where any input is processed (q0  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},
·         q0={a},
·         F={c}, and
Transition function δ as shown by the following table:
Present State
Next State for
Input 0
Next State for
Input 1
a
a
b
b
c
a
C
B
c

Its graphical representation would be as follows:


DFA – Graphical Representation

1 comment:

  1. Easy to understand thank you so much !!!

    ReplyDelete