Difference between the languages accepted by two DFAs with different initial state/accepting states? - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T08:22:50Z https://cs.stackexchange.com/feeds/question/10733 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/10733 9 Difference between the languages accepted by two DFAs with different initial state/accepting states? scaaahu https://cs.stackexchange.com/users/630 2013-03-24T03:40:45Z 2013-03-24T11:48:30Z <p><em>Recently, I asked a <a href="https://math.stackexchange.com/q/334581/17111">question</a> on Math SE. No response yet. This question is related to that question, but more technical details toward computer science.</em></p> <p>Given two DFAs $A = (Q, \Sigma, \delta, q_1, F_1)$ and $B = (Q, \Sigma, \delta, q_2, F_2)$ where the set of states, the input alphabet and the transition function of $A$ and $B$ are the same, the initial states and the final(accepting) states could be different. Let $L_1$ and $L_2$ be the languages accepted by $A$ and $B$, respectively.</p> <p>There are four cases:</p> <ol> <li>$q_1 = q_2$ and $F_1 = F_2$.</li> <li>$q_1 \neq q_2$ and $F_1 = F_2$.</li> <li>$q_1 = q_2$ and $F_1 \neq F_2$.</li> <li>$q_1 \neq q_2$ and $F_1 \neq F_2$.</li> </ol> <p>My question is</p> <blockquote> <blockquote> <p>What are the differences between $L_1$ and $L_2$ in cases 2, 3 and 4?</p> </blockquote> </blockquote> <p>I have a more specific question along this line,</p> <p>The transition monoid of an automaton is the set of all functions on the set of states induced by input strings. See <a href="http://en.wikipedia.org/wiki/Semiautomaton" rel="nofollow noreferrer">the page</a> for more details. The transition monoid can be regarded as a monoid acting on the set of states. See this <a href="http://en.wikipedia.org/wiki/Semigroup_action" rel="nofollow noreferrer">Wiki page</a> for more details.</p> <p>In many literatures, an automaton is called strongly connected when the monoid action is transitive, i.e. there is always at least one transition (input string) from one state to another state.</p> <blockquote> <blockquote> <p>If $A$ and $B$ are strongly connected automata, what are the differences between $L_1$ and $L_2$ in cases 2, 3 and 4 above?</p> </blockquote> </blockquote> <p>Any literatures discussing these issues in details?</p> <p>I have searched many books and articles and found nothing helpful so far. I believe I don't have the appropriate key words yet. Thus I am seeking help. Any pointers/references will be appreciated very much.</p> https://cs.stackexchange.com/questions/10733/-/10737#10737 8 Answer by Shaull for Difference between the languages accepted by two DFAs with different initial state/accepting states? Shaull https://cs.stackexchange.com/users/6890 2013-03-24T06:59:09Z 2013-03-24T11:48:30Z <p>Since $A,B$ are strongly connected, then if $q_1\neq q_2$, there exist words $p_1,p_2$ such that $\delta(q_1,p_1)=q_2$ and $\delta(q_2,p_2)=q_1$.</p> <p>Consider case 2, then $w\in L(A)$ iff $p_2w\in L(B)$, and $x\in L(B)$ iff $p_1 x\in L(A)$. So you can add a prefix to switch between languages.</p> <p>Consider case 3, then again - by strong connectivity there at most $|F_1|$ words $s_1,...,s_k$ such that for every $q_i\in F_1$ you have that $\delta(q_i,s_i)\in F_2$, and similarly for the other direction (from $B$ to $A$).</p> <p>Thus, you can compose suffixes to switch between languages.</p> <p>Combining these you can characterize the differences using prefixes and suffixes. For example, in case 4, $w\in L(B)$ iff $p_1 w s_i$ in $L(A)$ for some $s_i$ in a predetermined finite set.</p> <p>In fact, you can even say something interesting about these words: define $C$ to be the DFA where $q_1$ is the initial state and $q_2$ is the final state, then in case 2 you have $L(B)=L(C)\cdot L(A)$ (and similarly for the other direction).</p> <p>As for the suffixes, things are more involved, since you cannot predetermine in which final state you will end. I'm not sure you can write this as a concatenation, but you can write $L(B)=\bigcup_{q\in F_1}L(A_q)\cdot L(E_q)$ where $A_q$ is the DFA obtained from $A$ be setting $F=\{q\}$, and $E_q$ is a DFA that starts in $q$ with final states $F_2$.</p> <p>For case 4 you can combine the two.</p> <p>You may be concerned that this is not a real answer, but rather just a characterization of properties using words rather than states, but this is a typical answer in this field (similarly to the Myhill-Nerode theorem).</p>