Chapter 4: Formal Languages ~ 127
*
We prove L(G,,) = L l U L 2 as follows: If W E L j U L 2 , then 5 j => W or
52 => w. Therefore,
G,
Go
*
or 5 => 50 => w, l.e. W E L(G,,)
G u
G u
Thus, L j U L 2 ~ L(G,).
To prove that L(G,J ~ L l U L 2 • consider a derivation of w. The first step
should be 5 ~ 5 j or 5 ~ 52' If 5 ~ 51 is the first step, in the subsequent steps
5: is changed. As Vi.: ( l V;": :f:- 0, these steps should involve only the variables
of V:v and the productions we apply are in Pj. So 5 ~ w. Similarly, if the
G,
first step is 5 ~ 52, then 5 => 52 ~ w. Thus, L(G,,) =L l U L 2 . Also, L(G,J
G,
G,
is of type 0 or type 2 according as L 1 and L 2 are of type 0 or type 2. If A
is not in L j U L 2 , then L(G,,) is of type 3 or type 1 according as L j and L 2
are of type 3 or type 1.
Suppose A E L j • In this case, define
G" = (V~\, U V: v U {5, 5'}, I j U I2> P,!, 5')
where (i) S' is a new symbol, i.e. 5' e: V ' N U V',~ U {5}, and (ii) P" =
Pi U P 2 U {5' -? 5, 5 -? 5\> 5 -? 52}' So, L(G u ) is of type 1 or type 3
according as L] and L 2 are of type 1 or type 3. When A E L 2 , the proof is
similar. I
Theorem 4.6 Each of the classes ,10, L es \> L cf \> ;irl is closed under
concatenation.
Proof Let L j and L 2 be two languages of type i. Then, as in Theorem 4.5, we
get G j = CV:v, I\> P l , 51) and G 2 = (V':v , I:, P 2 , 52) of the same type i. We
have to prove that L1L: is of type i.
Construct a new grammar G eon as follows:
G eon = (V ' N U V\, U {5}, L 1 U L 2 , Peon' 5)
where 5 e: V~v U V(
Peon = P l U P2 U {5 -? 5 i 5 2 }
We prove L1L: = L(G eon )' If W = WjW: E LjL:, then
*
51 => lVI'
G,
So,
*
5 => 5 1 5 2 => WjW2
G eoa
G con
Therefore.
*
We prove L(G,,) = L l U L 2 as follows: If W E L j U L 2 , then 5 j => W or
52 => w. Therefore,
G,
Go
*
or 5 => 50 => w, l.e. W E L(G,,)
G u
G u
Thus, L j U L 2 ~ L(G,).
To prove that L(G,J ~ L l U L 2 • consider a derivation of w. The first step
should be 5 ~ 5 j or 5 ~ 52' If 5 ~ 51 is the first step, in the subsequent steps
5: is changed. As Vi.: ( l V;": :f:- 0, these steps should involve only the variables
of V:v and the productions we apply are in Pj. So 5 ~ w. Similarly, if the
G,
first step is 5 ~ 52, then 5 => 52 ~ w. Thus, L(G,,) =L l U L 2 . Also, L(G,J
G,
G,
is of type 0 or type 2 according as L 1 and L 2 are of type 0 or type 2. If A
is not in L j U L 2 , then L(G,,) is of type 3 or type 1 according as L j and L 2
are of type 3 or type 1.
Suppose A E L j • In this case, define
G" = (V~\, U V: v U {5, 5'}, I j U I2> P,!, 5')
where (i) S' is a new symbol, i.e. 5' e: V ' N U V',~ U {5}, and (ii) P" =
Pi U P 2 U {5' -? 5, 5 -? 5\> 5 -? 52}' So, L(G u ) is of type 1 or type 3
according as L] and L 2 are of type 1 or type 3. When A E L 2 , the proof is
similar. I
Theorem 4.6 Each of the classes ,10, L es \> L cf \> ;irl is closed under
concatenation.
Proof Let L j and L 2 be two languages of type i. Then, as in Theorem 4.5, we
get G j = CV:v, I\> P l , 51) and G 2 = (V':v , I:, P 2 , 52) of the same type i. We
have to prove that L1L: is of type i.
Construct a new grammar G eon as follows:
G eon = (V ' N U V\, U {5}, L 1 U L 2 , Peon' 5)
where 5 e: V~v U V(
Peon = P l U P2 U {5 -? 5 i 5 2 }
We prove L1L: = L(G eon )' If W = WjW: E LjL:, then
*
51 => lVI'
G,
So,
*
5 => 5 1 5 2 => WjW2
G eoa
G con
Therefore.