138 &2 Theory of Computer Science
(b) abba represents {abba}.
(c) As {01, 1O} is the union of {01} and {10}, we have {Ot 1O}
represented by 01 + 10.
(d) The set {A, ab} is represented by A + abo
(e) The set {abb, a, b, bba} is represented by abb + a + b + bba.
(f) As {A, 0, 00, 000, ... } is simply {O}*. it is represented by 0*.
(g) Any element in {L 11, 11 L ... } can be obtained by concatenating
1 and any element of {l}*. Hence 1(1)* represents {I, 11, Ill, ... }.
EXAMPLE 5.2
Describe the following sets by regular expressions:
(a) L 1 =the set of all strings of O's and l's ending in 00.
(b) L 2 = the set of all strings of O's and l's beginning with 0 and ending
with 1.
(c) L 3 = {A, 11, 1111, 111111, ... }.
Solution
(a) Any string in L] is obtained by concatenating any string over {O, I}
and the string 00. {O, I} is represented by 0 + 1. Hence L 1 is
represented by (0 + 1)* 00.
(b) As any element of L 2 is obtained by concatenating 0, any stling over
{O, I} and 1, L 2 can be represented by 0(0 + 1)* 1.
(c) Any element of L 3 is either A or a string of even number of l' s, i.e.
a string of the form (11)", 11 ~ O. So L 3 can be represented by (11)*.
5.1.1 IDENTITIES FOR REGULAR EXPRESSIONS
Two regular expressions P and Q are equivalent (we write P = Q) if P and
Q represent the same set of strings.
We now give the identities for regular expressions; these are useful for
simplifying regular expressions.
II
0 + R = R
I,
0R = R0 = 0
1 3
AR = RA = R
1 4
A* = A and 0* = A
Is
R+R=R
1 6
R*R* = R*
1 7
RR* = R*R
Is
(R*)* = R*
1 9
A + RR* = R* = A + R*R
1 10
(PQ)*P = P(QP)*