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.


For an integer $n$, consider the following DFA $A_n$ on the alphabet $\{a\}$. The set of states is $\{q_0,\ldots,q_{n-1}\}$. The initial state is $q_0$. All states are accepting. The transition function is $\delta(q_i,a) = q_{i+1}$, where we identify $q_n$ with $q_0$.

Do the relations of $A_2$ and $A_3$ refine each other?

  • $\begingroup$ I appreciate the quick reply. Perhaps I was using the wrong word, instead of "accepting" I meant "implementing" the same language. Does this make a difference? $\endgroup$ – Ben Apr 8 at 16:09
  • $\begingroup$ I don't think so. $\endgroup$ – Yuval Filmus Apr 8 at 17:01
  • $\begingroup$ however, A2 does refine A3. R_1 refine the equivalence relation R_2 if for each x,y that belongs to A if x,y belongs to R1 then they belong to R2. in your example A2 represents the letters a,b. that means that A3 includes a,b,c . No? sorry this is a new subject so it's going to take me some time to understand it $\endgroup$ – Ben Apr 8 at 17:35
  • 1
    $\begingroup$ All my automata are over the same alphabet, $\{a\}$. $\endgroup$ – Yuval Filmus Apr 8 at 17:39

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.