0
$\begingroup$

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}. enter image description here thank you for the help :)

$\endgroup$
2

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thank you, that works, Can you explain the thought process that led you to ponder this specific case? $\endgroup$ Commented Apr 20, 2023 at 11:02
  • $\begingroup$ 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. $\endgroup$
    – Steven
    Commented Apr 20, 2023 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.