CFL grammer questions

Question

I'm preparing to my test and I have 2 question in past test with no answers. Could you help me?

1. Prove or disprove the following claim. The language $$L=\{a^n\mid n!=k^2, k\ge 0\}$$ is a CFL.

I now that is not true, but I'm struggling prove it. I'm always stuck on the pumping lemma by choosing the right word.

2.Given a Content Free Language $L$ and its grammar $G$. Write a CFG $G’$ for a new language: $$\operatorname{AddLetter}(L)=\{uxv\mid x \in \Sigma, u,v \in \Sigma^*, u,v\in L\}\,.$$

I tried to get a correct grammar, but I don't know what I need to do with the $L$ language - I have no clue of its alphabet.

Answer 1

That first question is more about number theory than about formal languages and automata: $n!$ is never a perfect square if $n\ge 2$, so $L=\{\varepsilon,a\}$, which is even a regular language.

Added: J.-E. Pin has pointed out that the original pure text version, which I’d not seen, is ambiguous, and that the OP may well have intended $L$ to be the set $a^n$ such that $n$ is not the perfect square of any non-negative integer. If that’s the case, then of course the above answer is irrelevant, and it turns out that $L$ is not context-free.

One way to prove this is to apply Parikh’s theorem, which implies that a language over a one-letter alphabet is context-free if and only if it is regular. It is easy to use the pumping lemma for regular languages to show that $L$ is not regular. (It is perhaps even easier to use the pumping lemma for regular languages to show that $\{a\}^*\setminus L=\left\{a^{k^2}:k\ge 0\right\}$ is not regular and then use the fact that regular languages are closed under complementation.)

For the second question I think that you may assume that $\Sigma$ is the alphabet for both languages; $\operatorname{AddLetter}(L)$ is simply the set of words over $\Sigma$ that can be decomposed as $uxv$, where $u$ and $v$ are in $L$, and $x$ is any single character in the alphabet $\Sigma$. If $S$ is the initial non-terminal of $G$, give $G'$ a new initial symbol $S'$; then for each $x\in\Sigma$ the grammar $G'$ will have a production $S'\to \_x\_$, where I’ll leave it to you to fill in the two blanks.