1
$\begingroup$

( 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?

$\endgroup$
  • 1
    $\begingroup$ NFAs don't do anything randomly: they're nondeterministic, not random. We have a reference question about the differences. $\endgroup$ – David Richerby Aug 11 '16 at 8:43
  • $\begingroup$ Sorry, @DavidRicherby , my bad. Loose terminology. Wasn't really thinking about that, but rather focusing on expressing the question I was trying to ask. $\endgroup$ – John Forkosh Aug 11 '16 at 8:57
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Thanks, David. As soon as I saw your $Q\Sigma^\ast$, and read the surrounding sentence, I realized where you were going, and that I had indeed overlooked that -- and that it was pretty embarrassingly simple to have overlooked:) Moreover, your subsequent proof is indeed elegant, as requested. $\endgroup$ – John Forkosh Aug 11 '16 at 9:28
2
$\begingroup$

If you input the desired initial state (plus the actual input word), then you are not really using multiple initial states, right? Your proposed solution can easily be transformed into a DFA with a singular initial state: Add a state $\tilde{q_0}$, add transitions $\delta(\tilde{q_0}, q) = q$ (ok, I'm abusing notation here - your alphabet needs an element to represent each of your states in this case, but you could also encode them as words of whatever elements your alphabet has) to $\delta$ and make $\tilde{q_0}$ your initial state. Now the first input element selects the "actual initial state".

As for equivalence classes on the states: I'm not sure how they they help you there. Only trivial DFAs will have only one equivalence class on all of their states. Or are you talking about the "multiple initial states" belonging to different equivalence classes? In that case: It is easy to construct a DFA that accepts e.g. "a*" if it starts in $q_1$ and "b*" if it starts in $q_2$ - thus, $q_1$ and $q_2$ clearly belong to different equivalence classes. However, it is equally easy to construct a DFA that accepts "(a*|b*)" with a single initial state.

$\endgroup$
  • $\begingroup$ Thanks, Lukas. But $(a^\ast|b^\ast)$ is really a third language. What I want (and meant to say) is that $q_1\equiv q_2\Leftrightarrow L_{q_1}=L_{q_2}$, exactly the same subset of $\Sigma^\ast$. $\endgroup$ – John Forkosh Aug 11 '16 at 8:53
  • $\begingroup$ I'm afraid I don't understand your question then: $q_1 \equiv q_2 \Leftrightarrow L_{q_1} = L_{q_2}$ is just the definition of equivalence, is it not? So, assuming you have a DFA with "multiple initial states" $q_1, q_2, \dots q_k$, each accepting language $L_1, L_2, \dots L_k$ - which language exactly should the single-initial-state DFA that you are trying to prove existence of accept? $\endgroup$ – Lukas Barth Aug 11 '16 at 8:59
  • $\begingroup$ Yeah, that was my point -- unlike nfa's, there can't be any one dfa as discussed above, for the trivial reason that different $q_0$'s end up accepting different languages. But I thought maybe I'd somehow overlooked something or made some mistake. My question wasn't asking for a single dfa. Rather it had two parts: (1)am I correct that there's no such single dfa?, and if that's correct, then (2)is there an elegant way to characterize the equivalence classes? $\endgroup$ – John Forkosh Aug 11 '16 at 9:05

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.