The grammar can be modified to be of Type 1 by replacing its production rules with the following ones. E is assumed to be a new nonterminal symbol. A language is said to be a Type 2 language if there exists a Type 2 grammar that generates the language. The grammar of Example 1.2.7 is not a Type 1 grammar, and therefore also not a Type 2 grammar. The grammar can be modified to be a Type 2 grammar, by replacing its production rules with the following ones.
E is assumed to be a new nonterminal symbol.
A language is said to be a Type 3 language if there exists a Type 3 grammar that generates the language. An addition of a production rule of the form A Ba, or of the form B bb, to the grammar will result in a non-Type 3 grammar. Figure 1.2.3 illustrates the hierarchy of the different types of grammars. Figure 1.2.3 Hierarchy of grammars.