I was reading this wikipedia article for generating grammar. They have mentioned that for generating null string in the grammar we can have a rule

$$S \rightarrow \lambda$$

only if $S$ doesn't appear on the right of any production rule.

However in some examples like the following

$L(G) = \{ a^nb^n : n \ge 0 \}$. It has rules like

$$S \rightarrow aSb$$ $$S \rightarrow ab$$ $$S \rightarrow \lambda$$

Here $S$ is appearing on the right. So how come they are using $S \rightarrow \lambda$ rule?


It’s minor sloppiness. Change the productions to

$$\begin{align*} &S\to aTb\\ &S\to ab\\ &T\to aTb\\ &T\to ab\\ &S\to\lambda\;, \end{align*}$$

and you have essentially the same grammar written in a form that meets the requirement.

Added: There are really two different notions involved here. Let $\Sigma$ be the set of terminal symbols and $\mathscr{N}$ the set of non-terminal symbols, and let $S$ be the initial symbol. A context-sensitive production is one of the form $\alpha A\beta\to\alpha\gamma\beta$, where $\alpha,\beta\in(\Sigma\cup\mathscr{N})^*$, $\gamma\in(\Sigma\cup\mathscr{N})^+$, and $A\in\mathscr{N}$; it gets its name because the replacement of $A$ by $\gamma$ occurs only in the context $\alpha\_\beta$. A monotonic production is one of the form $\alpha\to\beta$, where $\alpha,\beta\in(\Sigma\cup\mathscr{N})^*$ and $|\alpha|\le|\beta|$; it gets its name from the fact that the length of the string in a derivation is monotonically non-decreasing. It’s a theorem that a language has a grammar consisting entirely of context-sensitive productions if and only if it has a grammar consisting entirely of monotonic productions. Call such languages purely context-sensitive for the moment.

Unfortunately, these productions don’t allow us to generate any language that contains the empty word. We’d like to make the context-sensitive languages a superset of the context-free languages, some of which do contain the empty word. To do this, we allow the production $S\to\lambda$ provided that $S$ does not appear on the righthand side of any production. It’s a sort of one-time exception to allow us to generate the empty word; it’s not intended to let us generate anything else that wasn’t already able to be generated. In other words, we want to generate only purely context-sensitive languages and languages that would be purely context-sensitive if they didn’t include the empty word.

The reason for not allowing $S$ to appear on the righthand side of any production is that if we don’t make that restriction, we can write grammars that generate languages that would not be purely context-sensitive even if we threw away the empty word. In fact, we could generate every language that can be generated by any formal grammar whatsoever. In terms of the Chomsky hierarchy, we could generate not only all of the type $1$ languages, but also all of the type $0$ languages. The restriction ensures that we really do generate only the type $1$ languages, i.e., those that are purely context-sensitive and those that would be purely context-sensitive if they didn’t include the empty word.

Some grammars that violate the restriction are easily seen to be equivalent to grammars that do not violate it; that’s the case with the one that you asked about, as I showed by replacing it with the grammar above. When that can obviously done, the grammar is sometimes sloppily referred to as a context-sensitive grammar, even though technically it isn’t.

  • $\begingroup$ Yeah thats fine I guess. But I didn't get how $S \rightarrow \lambda $ spoils it. I mean why is it that if S appears on the right we cannot use $S \rightarrow \lambda$ $\endgroup$ – rajan sthapit Sep 16 '12 at 0:10
  • $\begingroup$ @rajan: If you allow $S\to\lambda$ with $S$ on the right, a production like $A\to S$ effectively allows $A\to\lambda$. With that capability you can get Type $0$ formal languages as well as context-sensitive one. $\endgroup$ – Brian M. Scott Sep 16 '12 at 8:16
  • $\begingroup$ But we already have $S \rightarrow \lambda$ which makes it type 0 isn't it. I mean taking your example grammar in the answer. $\endgroup$ – rajan sthapit Sep 16 '12 at 9:05
  • $\begingroup$ @rajan: My example as I rewrote it is context-sensitive. Of course every context-sensitive grammar is also type $0$, but that isn’t what I meant in my previous comment: I meant that you could get all type $0$ langages, as well as the context-sensitive ones. $\endgroup$ – Brian M. Scott Sep 16 '12 at 9:11
  • $\begingroup$ I didn't get it. Can you elaborate more with some examples pls. That will help me understand it. Thanks for your help $\endgroup$ – rajan sthapit Sep 16 '12 at 13:13

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.