Skip to main content
added 141 characters in body; edited tags
Source Link
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

I have a logical question that I can't quite crack. Given two Automatas accepting the same language L, does one have to refine the other?:

Given two automata accepting the same language $L$, does one have to refine the other?

meaningIn other words, doesif R_a1$A_1$ and $A_2$ both accept $L$, with associated equivalence relations $R_{A_1}$ and $R_{A_2}$, does $R_{A_1}$ have to refine R_a2 equivalence relations? (or$R_{A_2}$, or vice versa)?

I am leaning toward the answer yes because if we have a regular language L$L$ which is accepted by an automaton A$A$, we can show that the relation R_A$R_A$ refines the relation R_L$R_L$, meaning Ra⊑Rl.$R_A \sqsubseteq R_L$, which means that both Ra1⊑Rl$R_{A_1} \sqsubseteq R_L$ and Ra2⊑Rl$R_{A_2} \sqsubseteq R_L$.

We are currently studying the Myhill-Nerode Theorem, so I'm guessing it has something to do something with it. I've tried combining few theorems together, but came out empty.

I have a logical question that I can't quite crack. Given two Automatas accepting the same language L, does one have to refine the other?

meaning, does R_a1 equivalence relations have to refine R_a2 equivalence relations? (or vice versa)

I am leaning toward the answer yes because if we have a regular language L which is accepted by an automaton A, we can show that the relation R_A refines the relation R_L, meaning Ra⊑Rl. which means both Ra1⊑Rl and Ra2⊑Rl.

We are currently studying the Myhill-Nerode Theorem so I'm guessing it has to do something with it. I've tried combining few theorems together but came out empty.

I have a logical question that I can't quite crack:

Given two automata accepting the same language $L$, does one have to refine the other?

In other words, if $A_1$ and $A_2$ both accept $L$, with associated equivalence relations $R_{A_1}$ and $R_{A_2}$, does $R_{A_1}$ have to refine $R_{A_2}$, or vice versa?

I am leaning toward the answer yes because if we have a regular language $L$ which is accepted by an automaton $A$, we can show that the relation $R_A$ refines the relation $R_L$, meaning $R_A \sqsubseteq R_L$, which means that both $R_{A_1} \sqsubseteq R_L$ and $R_{A_2} \sqsubseteq R_L$.

We are currently studying the Myhill-Nerode Theorem, so I'm guessing it has something to do with it. I've tried combining few theorems together, but came out empty.

Source Link
Ben
  • 11
  • 1

Given two DFA's accepting the same language, does one have to refine the other?

I have a logical question that I can't quite crack. Given two Automatas accepting the same language L, does one have to refine the other?

meaning, does R_a1 equivalence relations have to refine R_a2 equivalence relations? (or vice versa)

I am leaning toward the answer yes because if we have a regular language L which is accepted by an automaton A, we can show that the relation R_A refines the relation R_L, meaning Ra⊑Rl. which means both Ra1⊑Rl and Ra2⊑Rl.

We are currently studying the Myhill-Nerode Theorem so I'm guessing it has to do something with it. I've tried combining few theorems together but came out empty.