( This may be related to NFAs with more than one initial state )Consider a dfa $M$ with alphabet $\Sigma$ and states $Q$, typically also characterized by a specific initial state $q_0\in Q$. As the above-cited question points out, nfa's that nondeterministically select among several possible initial states can be converted to equivalent (wrt to their accepted language) nfa's with a unique initial state. And I'm asking if the same is true of dfa's, as follows.Instead of $M$'s input being only a tape/string $s\in\Sigma^\ast$, let its input be $(q_0,s)\in Q\times\Sigma^\ast$, i.e., you give it the initial state $q_0\in Q$ that you want it to start in, as well as a string.I'd think each possible $q_0\in Q$ defines a different language, call it $L_{q_0}\subseteq\Sigma^\ast$, accepted by $M$. But $Q$ can possibly be partitioned into equivalence classes, where all the states in a class accept the same $L$. But if there's more than one such class, then no single dfa with a unique $q_0$ starting state could represent this $M$.So, assuming that's more-or-less correct, my additional question is how to characterize the equivalence classes. That is, given $M$'s transition function, $\delta:\Sigma\times Q\to Q$, how would you determine whether $q\equiv q^\prime$ belong to the same class (besides, that is, individually working out the language each accepts)? Is there a more elegant way to do that?
DFA's with more than one initial state
finite automata
As Lukas points out, having multiple initial states is something of a red herring. You've defined your automaton to accept a subset of the strings that match the regular expression $Q\Sigma^*$ and that regular expression matches the language accepted by some ordinary DFA using the usual techniques. (Lukas gives an explicit construction in terms of the original automaton.)For equivalence, there is a standard polynomial-time technique used for state minimization for DFAs. Luca Trevisan has a good set of notes (PDF) on this, which I'll briefly summarize.  Let the automaton have state set $Q$, alphabet $\Sigma$ and transition function $\delta$.For a state $q$ and string $w$, write $\delta^*(q,w)$ for the state that you reach by starting at $q$ and reading $w$.  For states $p$ and $q$, write $p\equiv q$ to mean that $\delta^*(p,w)$ and $\delta^*(q,w)$ are either both accepting or both rejecting. This gives the same relation $\equiv$ that you give in the question.  We'll show how to compute $\equiv$.To do this, for any $n\geq 0$, define $p\equiv_n q$ in the same way as $p\equiv q$, except restricting $w$ to be of length at most $n$.  We'll compute the relations $\equiv_n$ inductively, and show that knowing a finite number of them is the same as knowing $\equiv$.First, note that $p\equiv_0 q$ if, and only if, $p$ and $q$ are both accepting or both rejecting so we can compute $\equiv_0$ easily.  Now, suppose we've already computed $\equiv_n$.  We claim that $p\equiv_{n+1}q$ if, and only if, $p\equiv_n q$ and $\delta(p,u)\equiv_n\delta(q,u)$ for all $u\in\Sigma$. Obviously, if $p$ and $q$ agree on all strings of length at most $n+1$, they must also agree on all strings of length at most $n$. For the second part, consider a string $uw$ where $|u|=1$ and $|w|=n$. We're saying that, for $p$ and $q$ to agree on $uw$, it must be that, after reading $u$, they move to states that agree on $w$.This allows us to construct the relations $\equiv_n$ for all $n$.  Finally, we claim that $\equiv_{|Q|}$ is actually the same relation as $\equiv$.  To see this, observe that every $\equiv_n$ is an equivalence relation and, furthermore, the procedure from moving from $\equiv_n$ to $\equiv_{n+1}$ can only split equivalence classes into smaller ones: it can never merge them. Also, if $\equiv_n$ and $\equiv_{n+1}$ are the same relation, then $\equiv_{n+i}$ is the same relation for all $i\geq 0$.  $\equiv_0$ has at most two equivalence classes.  Every step of the process either splits at least one equivalence class or is the end of the game: it doesn't split any class and nor does any future step. We can't split classes more than $|Q|$ times because, if we did, we'd have more equivalence classes than states, which is impossible. So it must be that $\equiv_{|Q|}$ is the same thing as $\equiv$ and we're done.