[Math] Confusion related to type 0 and type 1 grammar

context-free-grammarformal-languages

I have this confusion related to type 1 grammar and type 0 grammar
Lets say I have this type 1 grammar

$$
S \rightarrow aSb,
S \rightarrow ab
$$

Now if I want to generate the null string and I add the null string production rule like

$$S \rightarrow \lambda$$

It is being said that it is context 0 grammar and it could generate all possible languages. I didn't actually get that. Just because we add the null rule at the right side of the product containing S, how it destroys the grammar and makes it context 0 and produce all possible grammar. Can anyone please elaborate

Best Answer

When you add the production $S\to\lambda$ to that grammar, you no longer have a context-sensitive grammar, but the language that it generates is still context-sensitive. As I said in answering the earlier version of this question, there is no problem with this particular example: I showed you a context-sensitive grammar that generates the same language. The problem is a general one: if you allow $S\to\lambda$ in an otherwise context-sensitive grammar in which $S$ is allowed to appear on the righthand sides of productions, then you can generate all formal languages, not just context-sensitive languages.

The reason is that you can then get arbitrary productions that shorten the string $-$ productions that aren’t monotonic. For instance, to get $AB\to C$, just use $AB\to XB$, $XB\to XS$, and $X\to C$, where $X$ is used only in these productions. These are both context-sensitive, and if you also have $S\to\lambda$, you have the derivation $AB\Rightarrow XB\Rightarrow XS\Rightarrow X\Rightarrow C$. Absolutely any non-monotonic production can be simulated in this way. And the moment you allow arbitrary non-monotonic productions as well as monotonic ones, you’re allowing all productions and can generate any formal language whatsoever.

You asked me in the comments after the other question for a concrete example of a type $0$ language that isn’t context-sensitive. This would be a recursively enumerable language that isn’t recursive. Such languages exist, but it would take much more time than I can put in to give you the background for such an example.

Added: Consider for now only formal languages that do not contain the empty word. The context-sensitive languages of this type are those that can be generated by grammars in which every production is monotonic: if $\alpha\to\beta$ is a production in the grammar, then $|\alpha|\le|\beta|$. If you don’t limit yourself to monotonic productions, you can get all formal languages that don’t include the empty word. There are languages that don’t contain the empty word and are not context-sensitive: any grammar generating one of those languages must use at least one non-monotonic production.

However, we’d like to arrange matters so that ever context-free language is context-sensitive. Since context-free languages can contain the empty word, we have to find some way of allowing it into context-sensitive languages without letting anything else creep in. The easiest way to do this is to allow one special non-monotonic production, $S\to\lambda$, but only when $S$ does not appear on the righthand side of any production. If we do that, we get exactly the context-sensitive languages that we already had, without the empty word, and we also get each language that is one of those plus the empty word. That’s what we want. We don’t get any of the languages that aren’t context-sensitive.

If we allow ourselves to add the production $S\to\lambda$ and to have productions with $S$ on the righthand side, we can take any grammar $\Gamma$ with non-monotonic productions and replace it with a grammar $\Gamma'$ that has only one non-monotonic production, the special $S\to\lambda$, and still generates the same language as $\Gamma$. This means that if we allow ourselves to use the special production $S\to\lambda$, whose only intended purpose was to generate the empty word, and to have productions with $S$ on the righthand side, we can generate all formal languages with grammars that have only the one non-monotonic production. If we were simply to say that the context-sensitive languages are those that can be generated by a grammar in which all productions except $S\to\lambda$ are context-sensitive (or monotonic), there would be no point to the definition: we’d simply be defining the class of all formal languages. In order to get only the ones that we really do want to call context-sensitive, we have to impose that added restriction: if we need to use the production $S\to\lambda$, because the empty word is in our language and we have to get it somehow, then we cannot allow $S$ to appear on the righthand side of any production.

Sometimes, as in the Wikipedia example, you see this condition violated. This is sloppy. When it happens, however, you should be able fairly easily to modify the grammar, as I did in my first answer, to get an equivalent grammar that doesn’t violate the condition.

Related Question