How could we work out a grammar if we know the language? How could we work out a grammar if we know the language that is restricted to a special kind like CFL or CSL? For example, we know $$L=\{a^nb^nc^n \mid n \in \mathbb{N}\}$$ How can we get the grammar? Is there any algorithm?
PS: Language here means at least the recursively enumerable one, or computably enumerable one.
Theorem. There is no computable procedure which, given as input a Turing machine program $e$ that enumerates a c.e. set that happens to be a context-free language, outputs a context-free grammar for that language.
Proof. Let us denote by $W_e$ the set enumerated by program $e$. Suppose that there were such a computable procedure $e\mapsto g(e)$, where $g(e)$ is a context-free grammar for $W_e$, if indeed $W_e$ is a context-free language. (If $W_e$ is not context-free, then we do not assume $g(e)$ is meaningful or even that it converges.)
We define a certain computable function $f$. For any program $e$, let $W_{f(e)}$ be the c.e. set defined as follows. At first, we enumerate nothing into $W_{f(e)}$ until $g(e)$ converges and outputs a context-free grammar. At this point, if this grammar generates a non-empty language, then we continue to enumerate nothing into $W_{f(e)}$ and thereby ensure that $W_{f(e)}$ is empty. Alternatively, if the language generated by the grammar $g(e)$ is empty, then we ensure that $W_{f(e)}=\{0\}$, containing a single string. (Note that the emptiness problem for context-free grammars is computably decidable.)
By the recursion theorem, there is a particular program $e$ such that $W_e=W_{f(e)}$. Since $W_{f(e)}$ is either empty or a singleton, it follows that it is a context-free-language, and so $g(e)$ is defined. But by construction, we have ensured that $g(e)$ is a grammar for the empty language if and only if $W_e$ is non-empty. And so for this program, $g(e)$ is not a grammar for $W_e$. Contradiction. QED
