Are there any trivial examples of languages that cannot be produced by formal grammars?

Question

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.

Answer 1

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.

Answer 2

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.