1
$\begingroup$

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

2 Answers 2