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.