7
$\begingroup$

In order to characterize regular languages one finds the following definition useful:

Let $\Sigma$ be an alphabet and $L\subseteq\Sigma^*$. Say that $x,y\in\Sigma^*$ are $\equiv_L$-related, and write $x\equiv_L y$ if for all $z\in\Sigma^*$, $xz\in L$ if and only if $yz\in L$.

This is useful because $\equiv_L$ is an equivalence relation for every language $L$, and a language is regular if and only if the index of $\equiv_L$ (that is, the number of equivalence classes) is finite, as per Myhill-Nerode.

Now, I would like to define a binary operation $\cdot$ on $\Sigma^*_{/\equiv_L}$ as: $[x]\cdot[y]=[xy]$, where $[x]$ is the $\equiv_L$-equivalence class of $x$. This $\cdot$ will be operation that will give $\Sigma^*_{/\equiv_L}$ the structure of a monoid.

My question is: Is $\cdot$ well defined for an arbitrary language? How do I prove it?

So far, my approach has been trying to prove that the definition above is equivalent to:

Let $\Sigma$ be an alphabet and $L\subseteq\Sigma^*$. Say that $x,y\in\Sigma^*$ are $\sim_L$-related, and write $x\sim_L y$ if for all $w,z\in\Sigma^*$, $wxz\in L$ if and only if $wyz\in L$.

This is simple for regular languages, since one can take a minimal DFA and analyze its behaviour with strings that are $\sim_L$-related, but I'm struggling with a general proof. Maybe I'm missing something really simple, but in the paper where I found the "definition" of syntactic monoid, they just take $\Sigma_{/\equiv_L}$ and say "this is the monoid" without specifying the operation, and now that I'm trying to do it with full detail I'm completely stuck. Thanks in advance for your help!

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ By well-defined, do you mean $[x] = [y]$ implies, for all class $[z]$ that $[xz] = [yz]$ and $[zx] = [zy]$? This is clear for the first one, but the second one may be false. The second definition you give (with $\sim$) is the usual one and leads to a "well-defined" monoid. They are not "equivalent". $\endgroup$
    – Michaël Cadilhac
    Commented Sep 20, 2011 at 16:29
  • $\begingroup$ By well-defined I mean it doesn not depend on the representatives that I choose to write the classes. I'm starting to think they are not equivalent (working on an example right now), but in that case, it's a bit surprising that both versions are used indistinctly in different books and papers. $\endgroup$
    – Janoma
    Commented Sep 20, 2011 at 16:44
  • 1
    $\begingroup$ You may be interested in cstheory.stackexchange.com/questions/194/… BTW. $\endgroup$
    – Michaël Cadilhac
    Commented Sep 20, 2011 at 17:06
  • $\begingroup$ Thanks Michaël! So yes, I also found an example that shows they are different relations. I will try to see if the monoid is immediately well-defined when considering $\sim_L$, and maybe I will change the statement of my question. $\endgroup$
    – Janoma
    Commented Sep 20, 2011 at 18:04

1 Answer 1

Reset to default
10
$\begingroup$

The syntactic monoid of a language $L$, which is $\Sigma^{\ast}$ quotiented by $\sim_{L}$, is usually bigger than the set of equivalence classes of $\Sigma^{\ast}$ quotiented by $\equiv_{L}$. Informally, the Myhill-Nerode relation $\equiv_L$ only cares about the prefixes of a word $w$ (since it reflects the processing of $w$ by a DFA), while the syntactic monoid has to encode the information about all possible infixes of $w$ (otherwise you won't get the algebraic structure $[x]\cdot[y]=[x \cdot y]$)

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks a lot. I have yet to prove that $\cdot$ is well-defined, but now I see it shouldn't be too difficult. $\endgroup$
    – Janoma
    Commented Sep 20, 2011 at 18:50
  • 2
    $\begingroup$ Actually, if $|\Sigma^*/{\equiv_L}| = n$, then $|\Sigma^*/{\sim_L}| \leqslant n^n$, and this upper bound can be reached on a three-letter alphabet. $\endgroup$
    – J.-E. Pin
    Commented Aug 28, 2013 at 13:10

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.