# How to work out a grammar if we know the language?

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.

-
I´m not sure what you mean by algorithm here, since there are uncountably many possible inputs (languages). – Ramiro de la Vega Apr 3 '13 at 0:11
@Ramiro,thanks,I have edited the post to clarify what language means. Having published the post,actually,I think this question seems to be related to Gold theorem of languaged identification, – XL _at_China Apr 3 '13 at 1:03
If you intend to be asking a computability question, could you be more specific about the desired input/output? – Joel David Hamkins Apr 3 '13 at 1:11
Regarding your edit, then do you intend that the question is: given a Turing machine program that is known to enumerate a context free language, can we compute a grammar for it? – Joel David Hamkins Apr 3 '13 at 1:12
@Joel,thank you very much."the question is: given a Turing machine program that is known to enumerate a context free language, can we compute a grammar for it?",has been answered by Gold theorem of languag identification with "yes".And Even if we assumed, we have a Turing machine program that is known to enumerate a C.E. language, we can compute a grammar for it,by Gold theorem.But I do not know what the algorithm that works out the grammar is.Is there any algorithm(universal) that researcher has worked out?By the way,and can we make the condition on input more weak? – XL _at_China Apr 3 '13 at 1:34

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

-
@David,thank you. – XL _at_China Apr 3 '13 at 2:05
It looks like the proof would be the same also for other grammars (e.g., regular languages/expressions) such that the emptiness problem is decidable. Is that right? Very interesting! Thanks! – Matteo Mio Apr 3 '13 at 8:23
Matteo, yes, I think that's right. – Joel David Hamkins Apr 3 '13 at 10:27
This question has to be carefully decomposited into several ones:they have subtle difference,like the input,and are given different answers,especially to ones that have algorithms to find grammar. – XL _at_China Apr 4 '13 at 2:25
I agree completely, and that was the meaning of my comment on your question. I think there will be versions of the question where an algorithm is possible. – Joel David Hamkins Apr 4 '13 at 2:46