Chapter 4: Formal Languages );I, 121
Note: In a context-sensitive grammar G, we allow S ~ A for including A
in L(G). Apart from S -1 A, all the other productions do not decrease the
length of the working string.
A type 1 production epA Iff ~ dJalff does not increase the length of the
working string. In other words, i epA Iff I ::; ! ep alff I as a =;t: A. But if a ~ f3
is a production such that I a I ::; I13 I, then it need not be a type 1 production.
For example. BC ~ CB is not of type 1. We prove that such productions can
be replaced by a set of type 1 productions (Theorem 4.2).
Theorem 4.1 Let G be a type 0 grammar. Then we can find an equivalent
grammar G j in which each production is either of the form a ~ 13, where a
and 13 are strings of variables only. or of the form A ~ a, where A is a variable
and a is a terminal. G j is of type 1, type 2 or type 3 according as G is of type
L type 2 or type 3.
Proof We construct G j as follows: For constructing productions of G 1 ,
consider a production a -1 13 in G, where a or 13 has some terminals. In both
a and f3 we replace every terminal by a new variable C u and get a' and f3'.
Thus. conesponding to every a ~ 13, where a or 13 contains some terminaL we
construct a' ~ f3' and productions of the form C a ~ a for every terminal
a appearing in a or 13. The construction is performed for every such a ~ 13. The
productions for G] are the new productions we have obtained through the above
construction. For G] the variables are the variables of G together with the new
variables (of the form C,,). The terminals and the start symbol of G] are those
of G. G] satisfies the required conditions and is equivalent to G. So L(G) =
L(G]). I
Defmition 4.9 A grammar G = (Vy , L, P, S) is monotonic (or lengthincreasing) if every production in P is of the form a ~ 13 with I a I ::; I131
or 5 ~ A. In the second case,S does not appear on the right-hand side of any
production in P.
Theorem 4.2 Every monotonic grammar G is equivalent to a type 1 grammar.
Proof We apply Theorem 4.1 to get an equivalent grammar G]. We construct
G' equivalent to grammar G] as follows: Consider a production A j A 2 ... Am -1
B]B]. ... B n with 11 ::::: m in G!. If m = 1, then the above production is of
type 1 (with left and right contexts being A). Suppose In ::::: 2. Conesponding
to A]A 2 ... Am ~ B j B 2 ... B m we construct the following type 1 productions
introducing the new variables C j • C]., ..., C m .
Aj A 2 ... Am ~ C] A 2 ... Am
Note: In a context-sensitive grammar G, we allow S ~ A for including A
in L(G). Apart from S -1 A, all the other productions do not decrease the
length of the working string.
A type 1 production epA Iff ~ dJalff does not increase the length of the
working string. In other words, i epA Iff I ::; ! ep alff I as a =;t: A. But if a ~ f3
is a production such that I a I ::; I13 I, then it need not be a type 1 production.
For example. BC ~ CB is not of type 1. We prove that such productions can
be replaced by a set of type 1 productions (Theorem 4.2).
Theorem 4.1 Let G be a type 0 grammar. Then we can find an equivalent
grammar G j in which each production is either of the form a ~ 13, where a
and 13 are strings of variables only. or of the form A ~ a, where A is a variable
and a is a terminal. G j is of type 1, type 2 or type 3 according as G is of type
L type 2 or type 3.
Proof We construct G j as follows: For constructing productions of G 1 ,
consider a production a -1 13 in G, where a or 13 has some terminals. In both
a and f3 we replace every terminal by a new variable C u and get a' and f3'.
Thus. conesponding to every a ~ 13, where a or 13 contains some terminaL we
construct a' ~ f3' and productions of the form C a ~ a for every terminal
a appearing in a or 13. The construction is performed for every such a ~ 13. The
productions for G] are the new productions we have obtained through the above
construction. For G] the variables are the variables of G together with the new
variables (of the form C,,). The terminals and the start symbol of G] are those
of G. G] satisfies the required conditions and is equivalent to G. So L(G) =
L(G]). I
Defmition 4.9 A grammar G = (Vy , L, P, S) is monotonic (or lengthincreasing) if every production in P is of the form a ~ 13 with I a I ::; I131
or 5 ~ A. In the second case,S does not appear on the right-hand side of any
production in P.
Theorem 4.2 Every monotonic grammar G is equivalent to a type 1 grammar.
Proof We apply Theorem 4.1 to get an equivalent grammar G]. We construct
G' equivalent to grammar G] as follows: Consider a production A j A 2 ... Am -1
B]B]. ... B n with 11 ::::: m in G!. If m = 1, then the above production is of
type 1 (with left and right contexts being A). Suppose In ::::: 2. Conesponding
to A]A 2 ... Am ~ B j B 2 ... B m we construct the following type 1 productions
introducing the new variables C j • C]., ..., C m .
Aj A 2 ... Am ~ C] A 2 ... Am