Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Since the cardinality of the set of all languages that can be produced by a grammar is smaller (countably infinite) than the cardinality of the set of all languages (which is uncountable infinite) I'm wondering if there is an easy example for a language that cannot be produced by a grammar.

share|cite|improve this question
As someone who's trying to learn Danish I'm very tempted to give a non-mathematical answer to this question. – Tim May 11 '13 at 11:38
@Tim But he said "easy example", yet you seem to imply that Danish is hard... – fgp May 11 '13 at 15:24
up vote 2 down vote accepted

Any set which isn't recursively enumerable, I think.

To find such a set, you can e.g. look for a set which is recursively enumerable, but which isn't recursive. This corresponds to a set where you can write a program which outputs the elements of the set, one after another, but where you cannot decide (in finite time) whether a certain element is part of the set. The complement of such a set then cannot be recursively enumerable, because that'd make the original set recursive. (Because you could then start enumerating both the original set and its complement in parallel, and wait for the element in question to pop up on one of the two lists. It'd have to pop up eventually, so this algorithm always terminated)

The set of all eventually terminating programs in any turing-complete language is such a recursively enumerable set which isn't recursive, and thus the set of all non-terminating programs can not be recursively enumerable.

You can list all this programs via diagonalization, i.e. by first listing all one-character programs which terminate in at most one step, then all programs two-character programs which terminate in at most two steps, and so on. This makes the set of all eventually terminating programs recursively enumerable. Because of the undeciability of the halting problem, however, it cannot be recursive.

share|cite|improve this answer

If you mean grammars with a finite number of substitution rules I think these are equivalent in power to outputs of computer programs, so that the question asks for a set (of words) that is not recursively enumerable. Examples are as easy or hard or explicitly describable as for non-r.e. sets.

examples: The set of strings whose shortest generating program in C has an odd number of characters. The set of true sentences of first-order Peano arithmetic. The set of programs that do not halt. Any set higher in the arithmetic hierarchy than r.e. sets. The set of $n$ for which $n$-th bit of Chaitin's constant is $1$. The set of ...

None of these sets have any kind of explicit description, they are constructs that can be named in a theory of computer programs, or arithmetic, or set theory.

share|cite|improve this answer

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.