DFA (Deterministic finite automata)
DFA refers to deterministic finite automata. Deterministic refers to the
uniqueness of the computation. The finite automata are called deterministic
finite automata if the machine is read an input string one symbol at a time.
In DFA, there is only one path for specific input from the current state to the
next state.
DFA does not accept the null move, i.e., the DFA cannot change state without
any input character.
DFA can contain multiple final states. It is used in Lexical Analysis in Compiler.
In the following diagram, we can see that from state q0 for input a, there is
only one path which is going to q1. Similarly, from q0, there is only one path for
input b going to q2.
[Formal Definition]
Transition Diagram
A transition diagram or state transition diagram is a directed graph
which can be constructed as follows:
There is a node for each state in Q, which is represented by the
circle.
There is a directed edge from node q to node p labeled a
if δ(q, a) = p.
In the start state, there is an arrow with no source.
Accepting states or final states are indicating by a double circle.
Transition Table in Automata
Transition Table :
Transition function(∂) is a function which maps Q * ∑ into
Q . Here ‘Q’ is set of states and ‘∑’ is input of alphabets. To
show this transition function we use table called transition
table. The table takes two values a state and a symbol and
returns next state.
A transition table gives the information about –
Rows represent different states.
Columns represent input symbols.
Entries represent the different next state.
The final state is represented by a star or double circle.
The start state is always denoted by an small arrow.
Explanation of above table –
First column indicates all the present states, Next for input 0 and
1 respectively.
When the current/present state is q0, for input 0 the next state
will become q0 and for input 1 the next state is q1.
When the current state is q1, on input 0, the next state will
become q2, and for 1 input the next state is q1.
When the current state is q2 for input 0, the next state will
become q0, and for 1 input the next state is q1.
The small straight arrow on q0 indicates that it is a start state and
circle on to q3 indicates that it is a final state.
NFA (Non-Deterministic finite automata)
NFA stands for non-deterministic finite automata. It is
easy to construct an NFA than DFA for a given regular
language.
The finite automata are called NFA when there exist
many paths for specific input from the current state to
the next state.
Every NFA is not DFA, but each NFA can be translated
into DFA.
NFA is defined in the same way as DFA but with the
following two exceptions, it contains multiple next
states, and it contains ε transition.
In the following image, we can see that from state q0
for input a, there are two next states q1 and q2,
similarly, from q0 for input b, the next states are q0 and
q1. Thus it is not fixed or determined that with a
particular input where to go next. Hence this FA is called
non-deterministic finite automata.
Formal definition of NFA:
Example:
NFA with ∑ = {0, 1} accepts all strings with 01.
Difference between DFA and NFA :
