128 ];I, Theory of Computer Science
If >t' E L(G con )' then the first step in the derivation of w is S ~ SIS2'
As V;v n V'~ = 0 and the productions in G I or G 2 involve only the variables
*
(except those of the form A ~ a), we have W = WIW', where S => WI and
*
-
G]
S ~ W2' Thus L I L 2 = L(G em ,). Also, G con is of type 0 or type 2 according
as G 1 and G 2 are of type 0 or type 2. The above construction is sufficient when
G] and G 2 are also of type 3 or type 1 provided A ~ L] U L 2 .
Suppose G I and G 2 are of type 1 or type 3 and A E L] or A E Lo. Let
LIt =L 1 - {A}, L I
2 =L 2 - {A}. Then
{
L;L; U L;
L]L 2 = L;L; u L;
L;L; u L; u L; u {A}
if A is in L I but not in L 2
if A is in L 2 but not in L I
if A is in L] and also in L:c
As we have already shown that L csi and 1'rl are closed under union, L I L 2 is
of type 1 or type 3 according as L I and L 2 are of type 1 or type 3.
Theorem 4.7 Each of the classes L o , L cslo L cflo £rl is closed under the
transpose operation.
Proof Let L be a language of type i. Then L =L(G), where G is of type i.
We construct a new grammar C T as follows: G T =(VN> ~,pT, S), where the
productions of pT are constructed by reversing the symbols on L.R.S. and
R.R.S. of every production in P. Symbolically, cXt ~ f3T is in pT if a ~ f3 is
in P.
From the construction it is obvious that G
T is of type 0, 1 or 2 according
as G is of type 0, 1 or 2 and L(G
T
) = LT. For regular grammar, the proof is given
in Chapter 5.
It is more difficult to establish the closure property under intersection at
present as we need the properties of families of languages under consideration.
We state the results without proof. We prove some of them in Chapter 8.
Theorem 4.8 (i) Each of the families L o ], L cslo L rl is closed under
intersection.
(ii) L et1 is not closed under intersection. But the intersection of a contextfree language and a regular language is context-free.
4.6 LANGUAGES AND AUTOMATA
In Chapters 7 and 9, we shall construct accepting devices for the four types
of languages. Figure 4.1 describes the relation between the four types of
languages and automata: TM, LBA, pda, and FA stand for Turing machine,
linear bounded automaton, pushdown automaton and finite automaton,
respectively.
If >t' E L(G con )' then the first step in the derivation of w is S ~ SIS2'
As V;v n V'~ = 0 and the productions in G I or G 2 involve only the variables
*
(except those of the form A ~ a), we have W = WIW', where S => WI and
*
-
G]
S ~ W2' Thus L I L 2 = L(G em ,). Also, G con is of type 0 or type 2 according
as G 1 and G 2 are of type 0 or type 2. The above construction is sufficient when
G] and G 2 are also of type 3 or type 1 provided A ~ L] U L 2 .
Suppose G I and G 2 are of type 1 or type 3 and A E L] or A E Lo. Let
LIt =L 1 - {A}, L I
2 =L 2 - {A}. Then
{
L;L; U L;
L]L 2 = L;L; u L;
L;L; u L; u L; u {A}
if A is in L I but not in L 2
if A is in L 2 but not in L I
if A is in L] and also in L:c
As we have already shown that L csi and 1'rl are closed under union, L I L 2 is
of type 1 or type 3 according as L I and L 2 are of type 1 or type 3.
Theorem 4.7 Each of the classes L o , L cslo L cflo £rl is closed under the
transpose operation.
Proof Let L be a language of type i. Then L =L(G), where G is of type i.
We construct a new grammar C T as follows: G T =(VN> ~,pT, S), where the
productions of pT are constructed by reversing the symbols on L.R.S. and
R.R.S. of every production in P. Symbolically, cXt ~ f3T is in pT if a ~ f3 is
in P.
From the construction it is obvious that G
T is of type 0, 1 or 2 according
as G is of type 0, 1 or 2 and L(G
T
) = LT. For regular grammar, the proof is given
in Chapter 5.
It is more difficult to establish the closure property under intersection at
present as we need the properties of families of languages under consideration.
We state the results without proof. We prove some of them in Chapter 8.
Theorem 4.8 (i) Each of the families L o ], L cslo L rl is closed under
intersection.
(ii) L et1 is not closed under intersection. But the intersection of a contextfree language and a regular language is context-free.
4.6 LANGUAGES AND AUTOMATA
In Chapters 7 and 9, we shall construct accepting devices for the four types
of languages. Figure 4.1 describes the relation between the four types of
languages and automata: TM, LBA, pda, and FA stand for Turing machine,
linear bounded automaton, pushdown automaton and finite automaton,
respectively.