1
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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?

Improve this answer
$\endgroup$
4
  • $\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
    Commented Apr 8, 2021 at 16:09
  • $\begingroup$ I don't think so. $\endgroup$
    – Yuval Filmus
    Commented Apr 8, 2021 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
    Commented Apr 8, 2021 at 17:35
  • 1
    $\begingroup$ All my automata are over the same alphabet, $\{a\}$. $\endgroup$
    – Yuval Filmus
    Commented Apr 8, 2021 at 17:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.