0
$\begingroup$

While studying I've encountered this question written above. I am familiar to the closure properties of CFL, and even know that $$L=\{a^{j^2}|j\geqslant 0\}$$ ($a$ to the power of ($j$ to the power of $2$))
is one that answers the question, but I don't know how to prove that.

If anyone could explain it to me, it would be excellent!
Thank you.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

I think proving that $\text{Pref}(L)$ is CFL is the easiest part (it is even regular): ask yourself what are all prefixes of a word $a^{j^2}$.

Proving that $L$ is not CFL is done here.

You can use the pumping lemma for CFL or, even better, the pumping lemma for regular languages (using the fact that a CFL over a one-letter alphabet is a regular language).

Improve this answer
$\endgroup$
3
  • $\begingroup$ So we know that $Pref(L)$ is actually $a^*$ ,which of course, is regular? $\endgroup$
    – Ben Arviv
    Commented Apr 5, 2022 at 6:42
  • $\begingroup$ Yes. $\,\,\,\,$ $\endgroup$
    – Nathaniel
    Commented Apr 5, 2022 at 6:52
  • $\begingroup$ Great. Thank you very much, Nathaniel! $\endgroup$
    – Ben Arviv
    Commented Apr 5, 2022 at 7: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.