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
0 comments:
Post a Comment
Let us know your responses and feedback