I read the following argument showing that not every language is described by a grammar:

For a fixed alphabet $\Sigma$ and variables $V$ there are uncountable many languages over $\Sigma$ since the power set of $\Sigma^\ast$ is uncountable. But grammars are finite objects by construction and thus there are only countably many grammars. In total, there can only be countably many languages described by grammars. Hence, there are this uncountably many languages that cannot be described by grammars.

I understand the idea of the argument, however i am not convinced by how they show that there are only countably many grammars. What do they mean by "finite objects"? Couldn't one just take the set $\{ (V,\Sigma, P, S) | \; P\subseteq (V\cup \Sigma)^+ \times (V\cup \Sigma)^\ast,\; S\in V\}$, which is clearly uncountable, to get uncountably many grammars? Or do the languages that they generate fall together so often that we only get countably many languages generated by grammars in the end?

  • $\begingroup$ $\Sigma^*$ is uncountable if and only if $\Sigma$ is infinite. The set of languages is uncountable, but not for $\Sigma^*$ being uncountable, but for it being infinite (if $\Sigma$ is non-empty). $\endgroup$
    – plop
    Jul 26 '20 at 17:10
  • $\begingroup$ The set of production rules $P$ is required to be finite, just like the terminal and non-terminal symbols. $\endgroup$
    – plop
    Jul 26 '20 at 17:13
  • $\begingroup$ REPLY to 1st comment of plop: Oh yes. I edited my question accordingly. $\endgroup$ Jul 26 '20 at 17:13
  • $\begingroup$ REPLY to 2nd comment: Oh, I didn't know the rules have to be finite. I see now that if this is the case, we can easily enumerate all the grammars. Thanks. $\endgroup$ Jul 26 '20 at 17:15
  • $\begingroup$ A better question could be, why do we require the rules of a grammar be finite? $\endgroup$
    – John L.
    Jul 26 '20 at 18:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.