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

## 1 Answer

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?

• 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? – Ben Apr 8 at 16:09
• I don't think so. – Yuval Filmus Apr 8 at 17:01
• 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 – Ben Apr 8 at 17:35
• All my automata are over the same alphabet, $\{a\}$. – Yuval Filmus Apr 8 at 17:39