[Math] Confusion related to context sensitive grammar creation

context-free-grammarformal-languages

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?

Best Answer

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.

Related Question