[Solved]: Class of the language only containing the empty string?

Problem Detail: 

$L = \left \{ \epsilon \right \}$
Clearly this language is finite so this must be a regular language.
Now since every regular language is Context Sensitive, $L$ is a CSL.
We can define the grammar for $L$ as :
$S\rightarrow \epsilon$
Now since $L$ is a CSL, this grammar must be a Context Sensitive Grammar. But from the definition of a Context Sensitive Grammar:

A Context sensitive grammar is any grammar in which the left side of each production is not longer than the right side.

But here
$\left | S \right | > \left | \epsilon \right |$
This is contradictory.
I am unable to figure out what's wrong here.

Asked By : Romy

Answered By : phs

This issue is covered in wikipedia's article on noncontracting grammars. Such grammars do not allow deriving the empty string, which is no problem when one considers languages $L\subseteq A^+$. When one wants to allow the empty string, a special case is made and the rule $S\to\lambda$ is allowed with ugly side conditions ($S$ cannot appear in a right-hand side).

So the situation is that there are several available, mostly equivalent, definitions, that offer different tradeoffs between elegance, generality, ease of use, etc. This is a typical situation in mathematics. When you scratch the surface, the different definitions are there and they come with extra terminology, like "essentially noncontracting".

This may look confusing for newcomers but the good side is that it separates the important from the not-so-important details.

BTW your reasoning has a flaw. You say that the language is CSL (correct) and $S\to\lambda$ is a grammar for it (correct), thus that grammar is CS. That implication is incorrect. You can only deduce that there exists a CS grammar for it. But you are right in thinking that any such grammar must have a contracting rule.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/49948