2 replaced http://math.stackexchange.com/ with https://math.stackexchange.com/
source | link

Recently, I asked a questionquestion 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.

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.

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.

    Tweeted twitter.com/#!/StackCompSci/status/315731847894167553
1
source | link

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

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.