Problem Detail: 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.
Asked By : Sam Jones
Answered By : sdcvvc
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. $ $
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11889 Ask a Question Download Related Notes/Documents
