Let $L\subseteq \Sigma^*$ a Language

$R_L$ is the Myhill-Nerode-Relation of $L$

$\equiv_L$ is the Syntactic Congruence of $L$

$R_L$ and $\equiv_L$ are equivalence relations and are defined as follows :

$x\:R_L\:y \:\Leftrightarrow \: [\forall w\in\Sigma^* : xw\in L\Leftrightarrow yw\in L] $

$u\:\equiv_L\:v \:\Leftrightarrow \: [\forall x,y\in\Sigma^* : xuy\in L\Leftrightarrow xvy\in L] $

How to prove or disprove the following statements :

a) $[u_1]_{R_L} . [u_2]_{R_L} = [u_1u_2]_{R_L}$ is well-defined.

b) $[u_1]_{\equiv_L} . [u_2]_{\equiv_L} = [u_1u_2]_{\equiv_L}$ is well-defined.

  • $\begingroup$ It's been a while since I've done this sort of thing, but I'm quite sure you might want to consider using induction on the length of strings $u_1$ and $u_2$. $\endgroup$ – ted Dec 6 '17 at 8:57
  • 1
    $\begingroup$ I don't get what the question here is. What are a) and b) about? Where did you copy the exercise from? $\endgroup$ – Raphael Dec 6 '17 at 11:25
  • $\begingroup$ @Raphael unfortunately i don't either which is why i posted it here in the first place i did't copy it, it is an exercise from my Course (Formal Languages and Automata Theory in Germany). i edited the post maybe it well be clear now ? $\endgroup$ – proless8 Dec 6 '17 at 11:57
  • 1
    $\begingroup$ So it is a verbatim copy of an exercise problem. That means 1) you have to credit the authors, and 2) there is not really a question here. We're not a homework solving service; you'll have to try stuff for yourself and ask specific questions about where you get stuck. (The exercise itself is clear enough, just unfold the the definitions.) $\endgroup$ – Raphael Dec 6 '17 at 13:07

Let me try to guess where exactly is the problem here (without actually doing your exercise).

The point is that the operation is defined using equivalence classes, via the representatives of these classes. To show that the operation is well defined, you need to check that choosing other representatives (of the same classes) will give the same result of the operation.

So, in order to check that $[u_1]\cdot [u_2]$ is a well-defined operation, you need to show that if $[u_1]=[v_1]$ and $[u_2]=[v_2]$, then $[u_1u_2]=[v_1v_2]$.
(Or find a counter example in case the operations are not well-defined.)

Now it remains to plug-in the equivalence relations $R_L$ and $\equiv_L$ and see what happens.


(b) is correct.

Hint. I suffices to show that $\equiv_L$ is a congruence on the free monoid $A^*$, that is, $u \equiv_L v$ implies $xuy \equiv_L xvy$ for all $x, y \in A^*$.

(a) This operation is not well defined, because $R_L$ is only stable on one side: $u \mathop{R_L} v$ implies $xu \mathop{R_L} xv$ but does not necessarily implies that $uy \mathop{R_L} vy$.


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.