2
$\begingroup$

I am unsure I expressed myself correctly.

Anyway, I want to figure out what is the initial state of an automata who had its epsilon transitions removed and who was determinised.

In my text book it is stated, that suppose A is NFA with $\epsilon$-moves, suppose $q_0$ its initial state. Then the initial state of the equivalent DFA is the E-closure of $q_0$.

Yet in one of the softwares recommended by one of my teachers, $\epsilon$-NFA to DFA algorithm always puts the initial state as $q_0$ and not E-closure($q_0$).

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

There is no god-given algorithm for converting $\epsilon$-NFAs to DFAs. You can do it in several ways, and the results could well be different. It could be that your textbook's construction and the one in the software are simply different.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ True, but if you follow the fairly common naming convention that each DFA state gets named after the set of states that the NFA can be in, you would expect the epsilon closure to be used. If the OP wants to see a bit more of what the software is doing, make a NFA where q0 is not an accept state, but give it an epsilon transition to an accept state. No matter what the label, the DFA should start in an accept state. $\endgroup$
    – Algorithms with Attitude
    Commented Dec 29, 2016 at 21:16

Your Answer

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

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