# Example of L not regular language that suff(L) is regular

I can't find example of L not regular language that suff(L) is regular I tried something like this: {0^n1^n|n>= 0}, but i can't prove that it's suffix is regular

Suff(L) = {x ∈ Σ ∗ | ∃u ∈ Σ ∗ such that u · x ∈ L}. thank you for the help :)

• Since suffixes are just prefixes for the mirror language, the examples given in the answers to the following question are relevant: Non-regular language whose prefix language is regular but not the whole set of words Commented Apr 20, 2023 at 16:07
• The example $\{ 0^n 1^n \mid n\ge 0 \}$ from the question has suffixes that are non-regular: $\{ 0^k 1^n \mid n\ge k \ge 0 \} \cup 1^*$. Commented Apr 20, 2023 at 16:10

Let $$L = \{ 0^n \mid n \text{ is prime}\}$$. Suppose towards a contradiction that $$L$$ is regular and let $$p$$ be a prime not smaller than the pumping length of $$L$$. The pumping lemma ensures that there is some $$k$$ such that $$1 \le k \le p$$ and $$0^{p+ki} \in L$$ for all $$i \ge 0$$. Choosing $$i=p$$ we have that $$p+kp = p(k+1)$$, which is not prime. We conclude that $$L$$ is not regular.
To show that $$\textsf{Suff}(L)$$ is regular, let $$w = 0^{|w|}$$ be any word in $$\{0\}^*$$. Since there is a prime $$p \ge |w|$$, we have that $$0^{p-|w|} 0^{|w|} \in L$$, therefore $$w \in \textsf{Suff}(L)$$. Then, $$\{0\}^* \subseteq \textsf{Suff}(L) \subseteq \{0\}^*$$, i.e., $$\textsf{Suff}(L) = \{0\}^*$$, which is clearly regular.
• I just wanted a language that included all possible words as a suffix to (trivially) satisfy the property that $Suff(L)$ is regular. The first non-regular language I could think of with this property was the language of prime-length strings. This is well-known to be non-regular. Commented Apr 20, 2023 at 11:25