2
$\begingroup$

Can't seem to answer these questions, I'm sure the answers are out there somewhere but I don't really know what keywords to use to find them. Any answers or good sites/ documentation would be much appreciated. And please don't say wikipedia, the language used is a bit out of my comprehension at this moment.

  • Is it correct to assume that an NFA can be converted into multiple versions of a DFA?

  • Are there different methods for doing so and would they all be considered correct assuming they give different answers?

  • If an NFA has the transition relation d{ (q0,e,q1), (q1,e,q1), (q1,e,q2) } would it be correct to write it out as d(q0,e,q2)? (e standing for epsilon, q0 being initial state and q2 being final)

  • Is it correct to assume that every state in an NFA has a "hidden" e transition? Essentially can you assume that every state in an NFA has an e* transition.

  • Is it bad practice when converting to have multiple NFA states as one DFA state?

Alternatively is there some way I can test my conversions out and make sure they are correct either using a program or some other way.

Apologies for the noobiness of the questions.

$\endgroup$
  • $\begingroup$ What do you mean by a "hidden" $\epsilon$ transition? $\endgroup$ – GoodDeeds Feb 24 '17 at 17:56
  • $\begingroup$ Just clarified it a bit I hope. does every state have an e* transition? that we don't need to write out because it is implied. $\endgroup$ – Yiorgos Makridakis Feb 24 '17 at 18:29
  • 1
    $\begingroup$ The best way to address your difficulties is to set up a meeting with your TA or professor. Otherwise, please stick to one question per post. $\endgroup$ – Yuval Filmus Feb 24 '17 at 19:21
2
$\begingroup$

Answers to your questions in given order: (a) Yes, an NFA could in principle be converted into multiple distinct DFAs for the same language. Note however: There is always a unique DFA having a minimum number of states; other DFAs would have to be 'redundant' in some sense. (b) There may be different methods, though I am only aware of one. As long as the resulting DFA recognizes the same language, I would say the conversion method would be considered correct. (c) No, the expression d(q0,e,q2) would NOT be correct; however for every transition function $d$ there is a corresponding transitive closure $d^*$ for which that would be a valid expression. (d) No, it is not correct to assume the existence of 'hidden' e transitions; all defined transitions, e or not, must be given explicitly, but it is permissible to leave some transitions undefined (and any NFA-to-DFA converter must handle that case). (e) Not only is it NOT 'bad practice' to have multiple NFA states as one DFA state, that is the standard tactic used by the canonical NFA-to-DFA procedure.

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