Let $\Sigma$ be a finite alphabet. For a language $L \subseteq\Sigma^*$ we define:
$$Suff(L)= \left\{x\in\Sigma^*| \exists u \in \Sigma^*, u\cdot x \in L\right\}$$
Show an example of a language $L$ that is not regular for which $Suff(L)$ is regular.
I took $L=\left\{0^n1^n | n\geq 0 \right\}$.
It's easy to show that $L$ is not regular using the pumping lemma, however I tried to show that $Suff(L)$ is regular with no success.
I tried to split the possibilities of suffixes of every word $w \in L$ by cases.
If anyone have any idea how to show it, it would be great (meaybe I'm even wrong and my example is not true and that's why I can't prove it)
Asked
Active
Viewed 50 times
1
BridonElden
- 47
- 5
-
You might try: $L={1^p\mid p\text{ prime}}.$ The question didn't say it would work for any non-regular $L.$ – Thomas Andrews Mar 30 '23 at 14:28
-
1Interesting. I guess that in this case $Suff(L)=\left{1\right}^*$? – BridonElden Mar 30 '23 at 14:51