DFA and NFA are equivalent
Md and Mn are the equivalent ↔ L(Md) = L(Mn).
DFA and NFA are equivalent ↔
- For any DFA Md, there is an NFA Mn so that Md and Mn are equivalent.
- For any NFA Mn, there is a DFA Md such that Md and Mn are equivalent.
Equivalence proof
- For any DFA Md, there is an NFA Mn such that Md and Mn are equivalent
Proof: Let Md be any DFA. We desire to construct the NFA Mn that L(Mn) = L(Md).
From definitions of DFA and NFA, if M is a DFA then it is an NFA also.
Then, we let Mn = Md.
Therefore, L(Md) = L(Mn).
For any NFA Mn, there is a DFA Md that Md and Mn are equivalent.
Proof: Let Mn = (Q, Σ, δ, s, F) be any NFA. We want to construct a DFA Md so that
L(Md) = L(Mn).
First define closure of q, which is denoted by E(q).
Second, construct a DFA Md=(2Q, Σ, δ', E(s), F')
Finally, prove that ∀Σ∈w* ∃ f∈F (s,w) |-*Mn (f, ∈) ↔ ∃f'∈F '(E(s), ω) |- *Md (f' ,ε).
Email based Automata assignment help – homework help
The study of automata is an important area of theory of computation. Students feel trouble in solving automata questions. We at www.expertsmind.com offers Automata assignment help – Automata homework help and online tutoring with best qualified and experienced computer science tutor’s help. We cover all topics including Equivalence proof of DFA and NFA in assignment help – homework help service. Get solved problems in automata theory with step by step answers anytime from expert tutors at expertsmind.