5
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ I´m not sure what you mean by algorithm here, since there are uncountably many possible inputs (languages). $\endgroup$ Apr 3, 2013 at 0:11
  • $\begingroup$ @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, $\endgroup$ Apr 3, 2013 at 1:03
  • 2
    $\begingroup$ If you intend to be asking a computability question, could you be more specific about the desired input/output? $\endgroup$ Apr 3, 2013 at 1:11
  • $\begingroup$ 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? $\endgroup$ Apr 3, 2013 at 1:12
  • $\begingroup$ @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? $\endgroup$ Apr 3, 2013 at 1:34

1 Answer 1

6
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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! $\endgroup$
    – user11618
    Apr 3, 2013 at 8:23
  • $\begingroup$ Matteo, yes, I think that's right. $\endgroup$ Apr 3, 2013 at 10:27
  • $\begingroup$ 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. $\endgroup$ Apr 4, 2013 at 2:25
  • $\begingroup$ 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. $\endgroup$ Apr 4, 2013 at 2:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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