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.



How to work out a grammar if we know the language?
**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](http://en.wikipedia.org/wiki/Kleene%27s_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


