As per the title I was wondering if it's possible for a language $L \subseteq \Sigma^{*}$ to have $\Sigma^{*}$ as its syntactic monoid and if so could one give an example of such a language? I first thought that this was probably an easy question with a simple answer but I haven't been able to make much progress with it, maybe it has a simple answer and I am just overlooking it?

If we look at the syntactic congruence $\sigma_L = \{(w,z) \in \Sigma^{*} \times \Sigma^{*}: (\forall u, v \in \Sigma^{*}) \; uwv \in L \Leftrightarrow uzv \in L\}$ we see that in order to have $w \cong_{\sigma_{L}} z \Leftrightarrow w = z$ we must have that $(\forall w, z \in \Sigma^{*} \; w \not = z) \; (\exists u, v \in \Sigma^{*})\; uwv \in L \Leftrightarrow uzv \notin L$. Which seems like quite a strong condition. It's also clear that such a language couldn't be regular as it is known that a language is regular if and only if it has a finite syntactic monoid.

  • $\begingroup$ There is a mistake in your last statement: you just need the existence of a pair (u,v) to distinguish 2 elements (w,z), not all possible pairs. The negation of $\forall$ is $\exists$. The precise statement is: $(\forall w\neq z)(\exists (u,v)) uwv\in L \Leftrightarrow uzv\notin L$ $\endgroup$ – Denis May 8 '13 at 13:44
  • $\begingroup$ Yes, you're right. I have edited my question to fix that. $\endgroup$ – Sam Jones May 13 '13 at 15:45
  • $\begingroup$ The language of palindromes over a non-unary alphabet works: cs.stackexchange.com/a/33417/683. $\endgroup$ – Yuval Filmus May 6 '18 at 8:21

Consider $\{i\#a\#w: w_i = a\}$, where $i$ is an integer indicating index in a word (say, written in unary), $a$ is a single letter and $w$ is a word. This language says that at $i$-th place the word $w$ has letter $a$.

If $a \neq b$ then $a,b$ differ at some position $i$ and you can say $i \# a_i \# a \in L$ while $i \# a_i \# b \notin L$. Or, they can differ at length, but then you talk about the longer string.

This works for any alphabet with at least two characters; for unary alphabets you can use powers of two, squares etc. $ $

  • $\begingroup$ I don't think it works: as soon as you use three #, then you are out of the language, and all words become equivalent. More generally, any language assuming a particular number of occurence of some letter cannot have A* as syntactic monoid. $\endgroup$ – Denis May 13 '13 at 22:13
  • 1
    $\begingroup$ dkuper: No, $w$ can contain many $\#$. Only the first two $\#$ count in a word, they indicate division to $i,a$ and $w$ (in fact, the $\#$ between $a$ and $w$ is unneccessary). $\endgroup$ – sdcvvc May 13 '13 at 22:18
  • $\begingroup$ ah ok then it works, thanks (I cannot cancel the downvote until the answer is edited...) $\endgroup$ – Denis May 13 '13 at 22:24

It seems to work to take $L=\{ww: w\in\Sigma^* \text{and $|ww|$ is a power of $2$}\}$.

First, we can show that if $|u|>|v|$ then they are not equivalent. Indeed, there is $x$ such that $|uxux|$ is a big power of $2$, say $2^{|u|+|v|}$. Therefore, $uxux\in L$.

But then the length of $vxux$ cannot be power of $2$, because its difference to $2^{|u|+|v|}$ is only $|u|-|v|$. Therefore, if we take $y=xux$, we have $uy\in L$ and $vy\notin L$.

Now it suffices to show that words of the same length are not equivalent. Let $u\neq v$ with $|u|=|v|$, and let $x$ such that $|ux|$ is a power of $2$ (and then so is $|uxux|$). Then you can see that $(u,v)\notin\sigma_L$ because $uxux\in L$ and $uxvx\notin L$.

  • $\begingroup$ Could you explain why $uu \in L$, I'm not sure that the length of $uu$ has to be a power of 2. $\endgroup$ – Sam Jones May 13 '13 at 15:46
  • $\begingroup$ oups sorry, yes you're right we first need to complete u with a word x to reach a power of 2, I edit the answer $\endgroup$ – Denis May 13 '13 at 22:09

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.