Chapter 5: Regular Sets and Regular Grammars g 173
Then, >t' = 'VI' .. WI! where Wi E P*Q*. For simplicity take n = 2. (The result
can be extended by induction for any n). Then WJ = XIX2 .,. Xk' where
Xi E UP) and 11'2 =)'J)'2 ... )'1 where Yi E UQ), SO vI' =X1X2 ' , . XkY1Y2 ..• YI'
Each Xi or Yi is in L(P + Q). Hence 11' E L(P + Q)*, proving the first identity
in I] j. The second identity can be proved in a similar way.
Finally, we prove 1 12 ,
L((P + Q)R) = L(P + Q)L(R)
= (L(P) U L(Q»L(R)
UPR + QR) = L(PR) u L(QR)
= (L(P)L(R» u (L(Q)L(R»
But (A u B)C = AC u BC for A, B, C <;;;; L*. For. a string 11' in
(A u B)C is the concatenation of a string H'] in A or B and a string W2 in e.
If WI E A, then WjW2 E AC: if H'] E B, then WjW2 E Be. Hence W E AC u
Be. The other inclusion can be proved similarly. /12 follows from (A u B)e
= AC u Be.
EXAMPLE 5.34
Prove that P + PQ*Q = a*bQ* where P = b + aa*b and Q is any regular
expreSSiOn.
Proof
L.H.S. = PA + PQ*Q
= peA + Q*Q)
= PQ*
= (b + aa*b)Q*
= (Ab + aa*b)Q*
= (A + aa*)bQ*
= a*bQ*
= R.H.S.
by h
by 1 12
by 1 9
by definition of P
by I,
by 1]2
by /')
EXAMPLE 5.3 5
Construct a regular grammar accepting L = {w E {a, b} * I W is a string over
{a. b} such that the number of b's is 3 mod 4}.
Solution
We construct a DFA M accepting L directly. The symbol a can occur in any
place in 11' and b has to occur in 4k + 3 places, where k 2' : O. So we can have
stattOS q/, i = 0, 1. 2, 3. for remembering that the string processed so far has
4k. 4k + L 4k + 2 and 4k + 3 b's (k 2' : 0). q3 is the only final state. Also M
does not change state on reading a's. The state diagram representing M is
gIven in Fig. 5.35.
Then, >t' = 'VI' .. WI! where Wi E P*Q*. For simplicity take n = 2. (The result
can be extended by induction for any n). Then WJ = XIX2 .,. Xk' where
Xi E UP) and 11'2 =)'J)'2 ... )'1 where Yi E UQ), SO vI' =X1X2 ' , . XkY1Y2 ..• YI'
Each Xi or Yi is in L(P + Q). Hence 11' E L(P + Q)*, proving the first identity
in I] j. The second identity can be proved in a similar way.
Finally, we prove 1 12 ,
L((P + Q)R) = L(P + Q)L(R)
= (L(P) U L(Q»L(R)
UPR + QR) = L(PR) u L(QR)
= (L(P)L(R» u (L(Q)L(R»
But (A u B)C = AC u BC for A, B, C <;;;; L*. For. a string 11' in
(A u B)C is the concatenation of a string H'] in A or B and a string W2 in e.
If WI E A, then WjW2 E AC: if H'] E B, then WjW2 E Be. Hence W E AC u
Be. The other inclusion can be proved similarly. /12 follows from (A u B)e
= AC u Be.
EXAMPLE 5.34
Prove that P + PQ*Q = a*bQ* where P = b + aa*b and Q is any regular
expreSSiOn.
Proof
L.H.S. = PA + PQ*Q
= peA + Q*Q)
= PQ*
= (b + aa*b)Q*
= (Ab + aa*b)Q*
= (A + aa*)bQ*
= a*bQ*
= R.H.S.
by h
by 1 12
by 1 9
by definition of P
by I,
by 1]2
by /')
EXAMPLE 5.3 5
Construct a regular grammar accepting L = {w E {a, b} * I W is a string over
{a. b} such that the number of b's is 3 mod 4}.
Solution
We construct a DFA M accepting L directly. The symbol a can occur in any
place in 11' and b has to occur in 4k + 3 places, where k 2' : O. So we can have
stattOS q/, i = 0, 1. 2, 3. for remembering that the string processed so far has
4k. 4k + L 4k + 2 and 4k + 3 b's (k 2' : 0). q3 is the only final state. Also M
does not change state on reading a's. The state diagram representing M is
gIven in Fig. 5.35.