Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

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.

share|cite|improve this answer
I didn't get if we only have $AB \rightarrow C, AB \rightarrow XB, XB \rightarrow XS, X \rightarrow C$ then how will it produce $AB \rightarrow C$. I mean just considering the context sensitive grammar. how will it generate $AB \rightarrow C$ – rajan sthapit Sep 19 '12 at 3:13
Actually I didn't get this part sincerely "then you can generate all formal languages, not just context-sensitive languages". – rajan sthapit Sep 19 '12 at 3:15
@rajan: The point is to generate $C$ from $AB$ without having $AB\to C$, so we don’t have that production. We have $AB\to XB,XB\to XS,X\to C$, and $S\to \lambda$. With those we can produce the derivation $AB\Rightarrow XB\Rightarrow XS\Rightarrow X\Rightarrow C$ that I gave in my answer, exactly as if we had had the shrinking production $AB\to C$. – Brian M. Scott Sep 19 '12 at 3:15
I didn't get it. You have added $S \rightarrow \lambda$ when you had S on the right in the production rule $XB \rightarrow XS$. This has shrinkage that produces $AB \rightarrow C$. Therefore it is not good right? – rajan sthapit Sep 19 '12 at 12:49
@rajan: Yes. That example demonstrates why it’s not good. – Brian M. Scott Sep 19 '12 at 20:19

Saying "it can generate all types of languages" is, in my opinnion, incorrect. A Type 0 grammar can generate a Type 2 language. The type of the language is the type of the more restricted grammar that can be used to generate it, not the type of "any" grammar that can generate it. Of course, any language that is regular, context free or context sensitive can be generated by a Type 0 grammar (Type 1, 2 and 3 simply do not use contractable productions, but comply with the rules for Type 0 grammars).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.