122 ~ Theory of Computer Science
The above construction can be explained as follows. The production
A j A 2 ... A", ~ B]B 2 •.. B n
is not of type 1 as we replace more than one symbol on L.R.S. In the chain of
productions we have constructed, we replace A j by C l , A 2 by C 2 •• ., Am by
C",B m + i ••• B n . Afterwards. we start replacing C l by B 1 , C 2 by B 2 , etc. As we
replace only one variable at a time. these productions are of type 1.
We repeat the construction for every production in G] which is not of
type 1. For the new grammar G'. the variables are the variables of G l together
with the new variables. The productions of G' are the new type 1 productions
obtained through the above construction. The tenninals and the start symbol
of G' are those of G i .
G' is context-sensitive and from the construction it is easy to see that
L(G') = L(GJ = L(G).
Defmition 4.10 A type 2 production is a production of the fonn A ~ a,
where A E Vv and CI. E l Vv U L)*. In other words. the L.R.S. has no left
context or light context. For example. S ~ A.a, A ~ a. B ~ abc, A ~ A are
type 2 productions.
Definition 4.11 A grammar is called a type 2 grammar if it contains only
type 2 productions. It is also called a context-free granl<"'I1ar (as A can be
replaced by a in any context). A language generated by a context-free grammar
is called a type 2 language or a context-free language.
Definition 4.12 A production of the fonn A ~ a or A ~ aBo where
A.. B E \lv and a E I. is called a type 3 production.
Definition 4.13 A grammar is called a type 3 or regular grammar if all its
productions are type 3 productions. A production S ~ A is allowed in type 3
grammar. but in this case S does not appear on the right-hand side of any
production.
EXAMPLE 4.1 7
Find the highest type number which can be applied to the following
productions:
(a)
(b)
(el
S ~ Aa.
A
S ~ ASB Id,
S ~ as Iab
~ elBa.
A ~ aA
B ~ abc
The above construction can be explained as follows. The production
A j A 2 ... A", ~ B]B 2 •.. B n
is not of type 1 as we replace more than one symbol on L.R.S. In the chain of
productions we have constructed, we replace A j by C l , A 2 by C 2 •• ., Am by
C",B m + i ••• B n . Afterwards. we start replacing C l by B 1 , C 2 by B 2 , etc. As we
replace only one variable at a time. these productions are of type 1.
We repeat the construction for every production in G] which is not of
type 1. For the new grammar G'. the variables are the variables of G l together
with the new variables. The productions of G' are the new type 1 productions
obtained through the above construction. The tenninals and the start symbol
of G' are those of G i .
G' is context-sensitive and from the construction it is easy to see that
L(G') = L(GJ = L(G).
Defmition 4.10 A type 2 production is a production of the fonn A ~ a,
where A E Vv and CI. E l Vv U L)*. In other words. the L.R.S. has no left
context or light context. For example. S ~ A.a, A ~ a. B ~ abc, A ~ A are
type 2 productions.
Definition 4.11 A grammar is called a type 2 grammar if it contains only
type 2 productions. It is also called a context-free granl<"'I1ar (as A can be
replaced by a in any context). A language generated by a context-free grammar
is called a type 2 language or a context-free language.
Definition 4.12 A production of the fonn A ~ a or A ~ aBo where
A.. B E \lv and a E I. is called a type 3 production.
Definition 4.13 A grammar is called a type 3 or regular grammar if all its
productions are type 3 productions. A production S ~ A is allowed in type 3
grammar. but in this case S does not appear on the right-hand side of any
production.
EXAMPLE 4.1 7
Find the highest type number which can be applied to the following
productions:
(a)
(b)
(el
S ~ Aa.
A
S ~ ASB Id,
S ~ as Iab
~ elBa.
A ~ aA
B ~ abc