Chapter 5: Regular Sets and Regular Grammars J;;,l, 139
III
(P + Q)* = (P*Q*)* = (p* + Q*)*
1 12
(P + Q)R = PR + QR and R(P + Q) = RP + RQ
Note: By the 'set P' we mean the set represented by the regular expression P,
The following theorem is very much useful in simplifying regular
expressions (i.e. replacing a given regular expression P by a simpler regular
expression equivalent to P).
Theorem 5.1 (Arden' s theorem) Let P and Q be two regular expressions
over I. If P does not contain A, then the following equation in R, namely
R = Q + RP
(5.1)
has a unique solution (i.e. one and only one solution) given by R = QP*.
Proof Q + (QP*)P = Q(A + p*P) = QP* by 1 9
Hence (5.1) is satisfied when R =QP*. This means R =QP* is a solution
of (5.1).
To prove uniqueness. consider (5.1). Here, replacing R by Q + RP on the
R.H.S .. we get the equation
Q + RP = Q + (Q + RP)P
= Q + QP + RPP
= Q + QP + Rp2
= Q + QP + QP
2 +
+ QP
i + RP
i +
1
= Q(i\ + P + p 2 +
+ pi) + RP i +!
From (5.1),
R = Q(A + P + p
2 + ... + pi) + RP
i +!
for i ~ 0
(5.2)
We nmv show that any solution of (5.1) is equivalent to QP*. Suppose R
satisfies (5.1), then it satisfies (5.2). Let w be a string of length i in the set
R Then H" belongs to the set Q(A + P + p
2 + ... + pi) + RP
i +
1
. As P does
not contain A, RP i +
1 has no string of length less than i + 1 and so w is not
in the set RP+
1 . This means that w belongs to the set Q(A + P + p
2 + ...
+ P'J, and hence to QP*.
Consider a string w in the set QP*. Then tV is in the set QP
k for some
k ~ 0, and hence in Q(A + P + p
2 + . . . + p
k ). So w is on the R.H.S. of
(5.2). Therefore, w is in R (L.H.S. of (5.2). Thus Rand QP* represent the
same set. This proves the uniqueness of the solution of (5.1). I
Note: Henceforth in this text, the regular expressions will be abbreviated Le.
~xampte 5.3
(a) Giye an Le. for representing the set L of strings in which every °i s
immediately followed by at least two r s.
(b) Prove that the regular expression R =A + 1*(011)*(1* (011)*)* also
describes the same set of strings.
III
(P + Q)* = (P*Q*)* = (p* + Q*)*
1 12
(P + Q)R = PR + QR and R(P + Q) = RP + RQ
Note: By the 'set P' we mean the set represented by the regular expression P,
The following theorem is very much useful in simplifying regular
expressions (i.e. replacing a given regular expression P by a simpler regular
expression equivalent to P).
Theorem 5.1 (Arden' s theorem) Let P and Q be two regular expressions
over I. If P does not contain A, then the following equation in R, namely
R = Q + RP
(5.1)
has a unique solution (i.e. one and only one solution) given by R = QP*.
Proof Q + (QP*)P = Q(A + p*P) = QP* by 1 9
Hence (5.1) is satisfied when R =QP*. This means R =QP* is a solution
of (5.1).
To prove uniqueness. consider (5.1). Here, replacing R by Q + RP on the
R.H.S .. we get the equation
Q + RP = Q + (Q + RP)P
= Q + QP + RPP
= Q + QP + Rp2
= Q + QP + QP
2 +
+ QP
i + RP
i +
1
= Q(i\ + P + p 2 +
+ pi) + RP i +!
From (5.1),
R = Q(A + P + p
2 + ... + pi) + RP
i +!
for i ~ 0
(5.2)
We nmv show that any solution of (5.1) is equivalent to QP*. Suppose R
satisfies (5.1), then it satisfies (5.2). Let w be a string of length i in the set
R Then H" belongs to the set Q(A + P + p
2 + ... + pi) + RP
i +
1
. As P does
not contain A, RP i +
1 has no string of length less than i + 1 and so w is not
in the set RP+
1 . This means that w belongs to the set Q(A + P + p
2 + ...
+ P'J, and hence to QP*.
Consider a string w in the set QP*. Then tV is in the set QP
k for some
k ~ 0, and hence in Q(A + P + p
2 + . . . + p
k ). So w is on the R.H.S. of
(5.2). Therefore, w is in R (L.H.S. of (5.2). Thus Rand QP* represent the
same set. This proves the uniqueness of the solution of (5.1). I
Note: Henceforth in this text, the regular expressions will be abbreviated Le.
~xampte 5.3
(a) Giye an Le. for representing the set L of strings in which every °i s
immediately followed by at least two r s.
(b) Prove that the regular expression R =A + 1*(011)*(1* (011)*)* also
describes the same set of strings.