Theory of Computation
Section A
Section A
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
No comments:
Post a Comment