MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 7 down vote accepted

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

share|cite|improve this answer
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.