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


1 Answer 1


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

  • $\begingroup$ DFA can't have multiple initial states? $\endgroup$
    – Liana
    Jan 11, 2017 at 13:02
  • $\begingroup$ No. How would you like to define accepting an input in such automata? $\endgroup$ Jan 11, 2017 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, 2017 at 13:16
  • $\begingroup$ Doesn't it sound familiar to definition of accepting in NFA? :) $\endgroup$ Jan 11, 2017 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, 2017 at 13:27

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.