[Solved]: Difference between the languages accepted by two DFAs with different initial state/accepting states?

Problem Detail: 

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.

Asked By : scaaahu

Answered By : Shaull

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10733

 Ask a Question

 Download Related Notes/Documents