# Formal language without grammar

Definitions:

• Alphabet $Σ$: finite, non-empty set
• Language: subset of $Σ^*$
• Grammar: Unrestricted grammar (Chomsky Type 0)
• Language of a grammar: all words that can be produced by applying $P$ multiple times, starting from $S$

Grammars are finite, therefore there are only countable infinite of them. But there are uncountably infinite many languages. Each grammar can only describe one language. Therefore, there are languages without grammars.

Can you give an example for such a language without grammar?

I searched the internet, but strangely, I could not even find the question in context of formal language.

• Whenever you have a question about grammars, the Dragon book is a good place to look. Aug 26, 2013 at 2:09
• The same statement can be made about Turing machines: there are countably infinte TMs, but uncountably many languages. This is often used as the "intuition" for the existence of undecidable languages. Aug 26, 2013 at 2:56
• @jmite Intuition? That's a full-blown proof right there!
– Raphael
Aug 27, 2013 at 8:38
• I guess "intuition" isn't the right word. Explanation? Aug 27, 2013 at 16:42

I assume that by "grammar" you mean type-0 grammars. One can probably extend those to capture more languages.

Type-0 grammars are equivalent to Turing machines in expressive power. So, in order to show that a given language does not have a grammar, we can proceed as follows with suitable $L$:

Assume there was a grammar for $L$. Then, we could semi-decide the word problem of $L$. That contradicts the known fact that $L$ is not recursively-enumerable.

Note the semi here; assuming a grammar does not give us decidability, so the halting problem is not a suitable candidate -- we need a problem/language that is not even semi-decidable/recursively enumerable. From your computability background you should know that the complement of the (special) halting language, namely

$\qquad \overline{H} = \{ \langle M \rangle \mid M \text{ loops on } \langle M \rangle \}$,

is not semi-decidable. Thus, by the reduction outlined above, there is no (Chomsky) grammar for $\overline{H}$.

While the halting problem is a perfectly valid example of a language that a CFG can not capture, there is a huge middle ground of languages that are not context free but recursive (that is they can be solved by a Turing machine but can not be expressed by a CFG).

For example, you can use the pumping lemma for CFGs to show that the language $L = \{ a^i b^i c^i| i \in \mathbb N \}$ is not context free.

• The question does not talk about context-free languages.
– Raphael
Aug 26, 2013 at 8:30
• @Raphael: but the definition of grammar given by the OP corresponds to Type-2 grammars
– Vor
Aug 26, 2013 at 9:57
• @Vor Huh, true enough. Curious.
– Raphael
Aug 26, 2013 at 11:03
• This is the answer to the question I asked, but not the one I was interested in. Sorry for the confusion. :-/
– Yogu
Aug 26, 2013 at 20:16

Finally, I found an example: The non-halting programs. No Turing machine can determine that a program will not halt.

This is also why the type-0 languages are not closed under complementation.

• That's wrong; there are plenty of grammars for non-halting programs.
– Raphael
Aug 26, 2013 at 8:30
• How is the language of non-halting programs different from the complement of the halting language, which is what you provided as an example in your question?
– Yogu
Aug 26, 2013 at 20:14
• The complement of the halting language requires to check for non-termination at a specific position. The set of non-total programs is different in that regard; it can be recursively enumerated (proving this is a popular exercise in compatibility classes). Hint: For enumeration, it is sufficient to enforce non-termination in at least one position in a smart way -- no need to check. (I guess a full answer would be worth its own question here.)
– Raphael
Aug 27, 2013 at 8:41