3
$\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.

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

||cite|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.

||cite|improve this answer
$\endgroup$
  • 2
    $\begingroup$ The question does not talk about context-free languages. $\endgroup$ – Raphael♦ Aug 26 '13 at 8:30
  • $\begingroup$ @Raphael: but the definition of grammar given by the OP corresponds to Type-2 grammars $\endgroup$ – Vor Aug 26 '13 at 9:57
  • $\begingroup$ @Vor Huh, true enough. Curious. $\endgroup$ – Raphael♦ Aug 26 '13 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 '13 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.

||cite|improve this answer
$\endgroup$
  • $\begingroup$ That's wrong; there are plenty of grammars for non-halting programs. $\endgroup$ – Raphael♦ Aug 26 '13 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 '13 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 '13 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.