[Solved]: Formal language without grammar

ignougroup
Problem Detail: 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.

Asked By : Yogu

Answered By : Raphael

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/13923  Ask a Question  Download Related Notes/Documents