-2
$\begingroup$

If we convert an NFA to a DFA, is the regular expression of the DFA the same as the NFA?

I know the difference between an NFA and DFA and the algorithm to convert an NFA to DFA

$\endgroup$
1
$\begingroup$

For any DFA, NFA or regular expression, there is only one corresponding language. But for one language, there can be multiple corresponding DFA's, NFA's or regular expressions, so it is incorrect to talk about "the" regular expression of a DFA, but would be correct to say "a" regular expression associated to a DFA.

If you know a regular expression $e$ associated to a DFA $\mathcal{A}$, and a NFA $\mathcal{B}$ associated to the same DFA $\mathcal{A}$, then that means that all 3 objets share the same language:

$L(e) = L(\mathcal{A}) = L(\mathcal{B})$

In particular, that means that $e$ is also a regular expression associated to $\mathcal{B}$.

$\endgroup$
1
$\begingroup$

Depending on the algorithm to convert it.

We can construct an algorithm to convert an NFA to a regular expression by first converting it to a DFA, and then the DFA to a regex. This will yield that the regex for the DFA would be identical to that of the NFA (by definition of the algorithm)

But, you might find some other way to directly convert an NFA to a regex. Since there might be more than one different regular expressions for the language of the NFA, you can't be sure that the regex of the NFA will be the same as that of the DFA.

But an important remark is that even if the regular expressions are different, they always recognize the same language. Converting an NFA to a DFA and that to a regex doesn't change the language, thus any regex created from them must recognize the same language.

$\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.