Equivalence of DFA
Uploaded by
touseefaqEquivalence of DFA
Uploaded by
touseefaqEquivalence of DFA’s, NFA’s
DEFINITION: Two automata are equivalent if they recognize the same language.
A dfa can be become an nfa that accepts the same language. It is to be mentioned that in keeping
with the kleene’s theorem, if a language may be usual through a Fa, then there exists a transition
graph accepting that language. Since, an nfa is a transition graph as properly, consequently there
exists an nfa accepting the language prevalent by using the given Fa. In this case these FA and
NFA are said to be equivalent to each other.
Rather, for any nfa there may be a dfa that accepts the same language. The variety of states of the
dfa may be exponential inside the range of states of the nfa, hence, nfa’s receive exactly the regular
languages.
States of nfa Q, inputs Σ, transition function δN, state q0, and final states F,
States 2Q (Set of subsets of Q).
Inputs Σ.
Start state {q0}.
Final states = all those with a member of F.
The dfa states have names which are units of nfa states. But as a dfa state, an expression essential
to be deliver as a particular image, now not a hard and fast.
NFA N exists DFA D. AS L(D) = L(N).
This entails the subsection production, an significant case how an automata b can be widely
generate from some other automata a.
Given an NFA N = (QN, Σ, δN, q0 ,FN) we will construct a DFA D = (QD , Σ , δD ,{q0},FD) such
that
“L (D) = L (N)”
Let’s construct δD from the NFA
3
4
STATES a b
A=3 B = {3,1} C= {3,2}
B = {3,1} D= {1,3,4} C= {3,2}
C= {3,2} B = {3,1} E = {3,2,4}
*D= {1,3,4} D= {1,3,4} E = {3,2,4}
*E = {3,2,4} D= {1,3,4} E = {3,2,4}
Equivalent DFA
a
3 4
3 4
Why we Need to Convert NFA to DFA?
The concepts presented by DFAs is easy to be translated into any physical machine or software but as
compared to DFAs, NFA a bit complex and difficult to translate into and practical implementation due its
complexity. It’s possible to find its equivalent through DFA.
Programs usually require all possible transitions and states for given machine.NFAs as we know have all
transitions that travel through any no. of states for each given input, that’s the main issue for computer
program as it requires accurate one transition for given input.so the process of conversion of NFA to DFA
removes this uncertainty and enable the program to compile its construction.
In non determistic automata, back down is not always possible. While back down or backtracking is possible
in DFA.
NFA is implementable so it is required to convert it into DFA to be implementable.
A string recognized Non deterministic automata, if one of all transition is results on final state while a string
is recognized if its transition is on final state.
NFA cause ambiguity which will be a cause of uncertainty for machine. In order to remove this ambiguity
it must be convert into its equivalent Dfa
NFA accepts empty string which not acceptable in real world so it must not accepts empty string due to
which it have to be converted into DFA.
NFA provide several un-finale states and accept empty string due to which it’s not possible for it to be
distinct, while its equivalent Dfa is district.
As we recognize that dfa transition characteristic is fulfilled, the nfa transition characteristic but the
transition characteristic of nfa does no longer fulfill the situation of dfa transition feature.