How can I formally define 𝛿* for a dfa with multiple initial states? I know that the δ formal definition for NFA is δ: Q × ∑ → 2^Q and for DFA it's δ : Q × Σ → Q but what should I do if there is multiple initial states?How can I take into consideration all the options for the initial state?It seem like it should combine the NFA definition and DFA definition.. δ: 2^Q × ∑ → Q maybe?but it doesn't seem right neither.

I would appreciate any help I can get on this matter


If you have multiple initial states, then this automata is non-deterministic.

  • $\begingroup$ DFA can't have multiple initial states? $\endgroup$ – Liana Jan 11 '17 at 13:02
  • $\begingroup$ No. How would you like to define accepting an input in such automata? $\endgroup$ – Szymon Stankiewicz Jan 11 '17 at 13:06
  • $\begingroup$ For every input w if there is a transition function 𝛿* starting from one of the initial states and ending with one of the final states $\endgroup$ – Liana Jan 11 '17 at 13:16
  • $\begingroup$ Doesn't it sound familiar to definition of accepting in NFA? :) $\endgroup$ – Szymon Stankiewicz Jan 11 '17 at 13:17
  • $\begingroup$ The problem is it's defined in the question as a DFA with multiple initial states..I thought that I might be missing on something here..since I know that for every DFA there is an NFA but I'm not sure that the opposite is also right,I'll try considering it as a NFA :) $\endgroup$ – Liana Jan 11 '17 at 13:27

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.