Automata
Automata
Automata
In DFA, for each input symbol, one can determine the state to which the machine will move.
Hence , it is called Deterministic Finite Automaton. As it has a finite number of state , the
machine is called Deterministic Finite Machine or Deterministic Finite Automaton.
In NFA can be represented by 5 tuple :-
Q is a finite of state.
Ʃ is a finite set of symbols called the alphabet.
Ᵹ is the transition function where Ʃ x 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).
In NFA, for a particular input symbol ,the machine can move to any combination of the
states in the machine. In odher word , the exact state to which the machine moves cannot
be determined. Hence, it is Non-deterministic finite automaton.
As it is has finites number of states, the machine is called Non-deterministic Finite
Automaton.
In NFA can be represented by 5 tuple :-
Q is a finite of state.
Ʃ is a finite set of symbols called the alphabet.
Ᵹ is the transition function where Ʃ x Q →2 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).
1
C 0 B
0
0 1
0,1 E
A
0,1 0
0
q Ᵹ (q,0) Ᵹ (q,1)
a {a,b,c,d,e} {d,e}
b {c} {e}
c Φ {b}
d {e} Φ
e Φ Φ
q Ᵹ (q,0) Ᵹ (q,1)
a {a,b,c,d,e} {d,e}
{a,b,c,d,e} {a,b,c,d,e} {b,d,e}
q Ᵹ (q,0) Ᵹ (q,1)
a {a,b,c,d,e} {d,e}
{a,b,c,d,e} {a,b,c,d,e} {b,d,e}
{d,e} E D
q Ᵹ (q,0) Ᵹ (q,1)
a {a,b,c,d,e} {d,e}
{a,b,c,d,e} {a,b,c,d,e} {b,d,e}
{d,e} E D
{b,d,e} {c,e} E
q Ᵹ (q,0) Ᵹ (q,1)
a {a,b,c,d,e} {d,e}
{a,b,c,d,e} {a,b,c,d,e} {b,d,e}
{d,e} E D
{b,d,e} {c,e} E
e Φ Φ
q Ᵹ (q,0) Ᵹ (q,1)
a {a,b,c,d,e} {d,e}
{a,b,c,d,e} {a,b,c,d,e} {b,d,e}
{d,e} E D
{b,d,e} {c,e} E
e Φ Φ
d E Φ
q Ᵹ (q,0) Ᵹ (q,1)
a {a,b,c,d,e} {d,e}
{a,b,c,d,e} {a,b,c,d,e} {b,d,e}
{d,e} E D
{b,d,e} {c,e} E
e Φ Φ
d E Φ
{c,e} Φ B
q Ᵹ (q,0) Ᵹ (q,1)
a {a,b,c,d,e} {d,e}
{a,b,c,d,e} {a,b,c,d,e} {b,d,e}
{d,e} E D
{b,d,e} {c,e} E
e Φ Φ
d E Φ
{c,e} Φ B
b C E
This table DFA
q Ᵹ (q,0) Ᵹ (q,1)
a {a,b,c,d,e} {d,e}
{a,b,c,d,e} {a,b,c,d,e} {b,d,e}
{d,e} E D
{b,d,e} {c,e} E
e Φ Φ
d E Φ
{c,e} Φ B
b C E
c Φ B
1 {b,d,e
{a,b,c,d,e}
0 1
{d,e} {c,e}
1
1 1
{c}
{a} {b} 0
0
1 1
{e}
{d} 0