9
$\begingroup$

Recently, I asked a question on Math SE. No response yet. This question is related to that question, but more technical details toward computer science.

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.

There are four cases:

  1. $q_1 = q_2$ and $F_1 = F_2$.
  2. $q_1 \neq q_2$ and $F_1 = F_2$.
  3. $q_1 = q_2$ and $F_1 \neq F_2$.
  4. $q_1 \neq q_2$ and $F_1 \neq F_2$.

My question is

What are the differences between $L_1$ and $L_2$ in cases 2, 3 and 4?

I have a more specific question along this line,

The transition monoid of an automaton is the set of all functions on the set of states induced by input strings. See the page for more details. The transition monoid can be regarded as a monoid acting on the set of states. See this Wiki page for more details.

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.

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?

Any literatures discussing these issues in details?

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.

$\endgroup$
  • $\begingroup$ What do you mean by "what are the differences"? You want to know whether $L_1$ and $L_2$ can/must differ in the cases 2,3,4? $\endgroup$ – Hendrik Jan Mar 24 '13 at 18:14
  • $\begingroup$ @HendrikJan If you read the answer Shaull provided below, you'll understand $L_1$ and $L_2$ can differ. (He used $L(A)$ and $L(B)$). I don't know whether they must differ. That's part of my question. I asked "what are the differences?". I did not imply they must differ. $\endgroup$ – scaaahu Mar 25 '13 at 1:56
8
$\begingroup$

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$.

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.

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$).

Thus, you can compose suffixes to switch between languages.

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.

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).

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$.

For case 4 you can combine the two.

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).

$\endgroup$
  • $\begingroup$ I understand your answer. My problem is, e.g. such $p_1$ is not unique, i.e. there are many $p_1$ such that $\delta(q_1,p_1) = q_2$. Thus there are many prefixes in the difference between $L(A)$ and $L(B)$. Do we have more precise answers? $\endgroup$ – scaaahu Mar 24 '13 at 7:14
  • $\begingroup$ I edited the answer with some more precise information. $\endgroup$ – Shaull Mar 24 '13 at 7:29
  • $\begingroup$ I truly like the idea of that DFA $C$. I think I have a rough idea how to tackle case 3 and 4. Thanks a lot. I'll wait a while before I accept this answer. $\endgroup$ – scaaahu Mar 24 '13 at 7:38
  • $\begingroup$ Please note additional edits in the post. $\endgroup$ – Shaull Mar 24 '13 at 11:48
  • 1
    $\begingroup$ Good idea. You're taking one final state at a time then taking the union. Hope my interpretation is correct. $\endgroup$ – scaaahu Mar 24 '13 at 12:07

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.