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.

Improve this question
$\endgroup$
4
  • $\begingroup$ What do you mean by a "hidden" $\epsilon$ transition? $\endgroup$
    – GoodDeeds
    Commented Feb 24, 2017 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
    Commented Feb 24, 2017 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
    Commented Feb 24, 2017 at 19:21
  • $\begingroup$ Re (c), it is not right. If you change the NFA, you (obviously) get a different one. It might accept the same language, but still is another one. $\endgroup$
    – vonbrand
    Commented Feb 23, 2020 at 19:52

1 Answer 1

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

Improve this answer
$\endgroup$

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.