1
$\begingroup$

In the context of studying the conversion from an NFA to the equivalent DFA, I came across the following NFA, which accepts all strings over the alphabet $\{0,1\}$ which contain $01$:

enter image description here

After I converted the NFA to the equivalent DFA, it became:

enter image description here

The issue is that the NFA accepts the string $101$ but the DFA doesn't.

Is my conversion wrong or is there something I am missing about the NFA to DFA conversion?

$\endgroup$
5
  • $\begingroup$ How does the NFA accept 101? I think the NFA only accepts words starting with 01. $\endgroup$
    – atin
    Apr 12 '21 at 11:25
  • 1
    $\begingroup$ I think your NFA might be missing a self-loop in the initial state (currently your NFA is also a DFA). $\endgroup$
    – Shaull
    Apr 12 '21 at 11:26
  • $\begingroup$ As @Shaull pointed currently your NFA is also an incomplete DFA and the DFA you obtained after conversion is the complete version of the NFA (or DFA) $\endgroup$
    – atin
    Apr 12 '21 at 11:33
  • 1
    $\begingroup$ If the language by your DFA differs from the language accepted by your NFA then you did something wrong during the conversion. $\endgroup$
    – Steven
    Apr 12 '21 at 13:02
  • $\begingroup$ Two automata are equivalent, by definition, if they accept the same language. $\endgroup$ Apr 12 '21 at 16:53
0
$\begingroup$

By definition, two automata are equivalent if they accept the same language.

In your case, the DFA you construct is indeed equivalent to the NFA you start with. Both of them accept all strings starting with $01$. In particular your NFA does not accept $101$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.