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?

Improve this question
$\endgroup$
5
  • $\begingroup$ How does the NFA accept 101? I think the NFA only accepts words starting with 01. $\endgroup$
    – atin
    Apr 12, 2021 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, 2021 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, 2021 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, 2021 at 13:02
  • $\begingroup$ Two automata are equivalent, by definition, if they accept the same language. $\endgroup$
    – Yuval Filmus
    Apr 12, 2021 at 16:53

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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