6
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Whenever you have a question about grammars, the Dragon book is a good place to look. $\endgroup$
    – Shitikanth
    Aug 26, 2013 at 2:09
  • 1
    $\begingroup$ 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. $\endgroup$
    – jmite
    Aug 26, 2013 at 2:56
  • 2
    $\begingroup$ @jmite Intuition? That's a full-blown proof right there! $\endgroup$
    – Raphael ♦
    Aug 27, 2013 at 8:38
  • $\begingroup$ I guess "intuition" isn't the right word. Explanation? $\endgroup$
    – jmite
    Aug 27, 2013 at 16:42

3 Answers 3

Reset to default
6
$\begingroup$

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}$.

Improve this answer
$\endgroup$
3
$\begingroup$

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.

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

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ That's wrong; there are plenty of grammars for non-halting programs. $\endgroup$
    – Raphael ♦
    Aug 26, 2013 at 8:30
  • $\begingroup$ 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? $\endgroup$
    – Yogu
    Aug 26, 2013 at 20:14
  • $\begingroup$ 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.) $\endgroup$
    – Raphael ♦
    Aug 27, 2013 at 8:41

Your Answer

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

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