Chapter 5: Regular Sets and Regular Grammars ~ 137
Notes: (1) We use x for a regular expression just to distinguish it from the
symbol (or string) x.
(2) The parentheses used in Rule 5 influence the order of evaluation of
a regular expression.
(3) In the absence of parentheses, we have the hierarchy of operations as
follows: iteration (closure). concatenation, and union. That is, in evaluating a
regular expression involving various operations. we perform iteration first, then
concatenation. and finally union. This hierarchy is similar to that followed for
arithmetic expressions (exponentiation. multiplication and addition).
DefInition 5.1 Any set represented by a regular expression is called a regular
set.
If for example, a, bEL. then (i) a denotes the set {a}, (ii) a + b denotes
{a, b}, (iii) ab denotes {ab}, (iv) a* denotes the set {A. a, aa. aaa, ... } and
(v) (a + b)* denotes {a, b}*.
The set represented by R is denoted by L(R),
Now we shall explain the evaluation procedure for the three basic
operations. Let R j and R: denote any two regular expressions. Then (i) a
string in L(R j + R:) is a string from R] or a string from R:; (ii) a string in
L(R j R 2 ) is a string from R j followed by a string from R,. and (iii) a string
in L(R*) is a string obtained by concatenating 11 elements for some II 2: O.
Consequently. (i) the set represented by R j + R 2 is the union of the sets
represented by R] and R 2 • (ii) the set represented by RjR: is the concatenation
of the sets represented by R j and R:. (Recall that the concatenation AB of sets
A and B of strings over I is given by AB = {H'(W: IWj E A, 1~': E B}, and
(iii) the set represented by R* is {WI"': ... It',JWi is in the set represented by
Rand Il 2: O.} Hence.
L(R j + R 2 ) = L(R]) u L(R 2 ),
L(R]R:) = L(RI)L(R:)
L(R*) = (L(R»)*
Also.
L(R*) = (L(R)* = U L(R)"
11=0
L(0) = 0,
L(a) = {a}.
Note: By the definition of regular expressions, the class of regular sets over
I is closed under union, concatenation and closure (iteration) by the conditions
2. 3. 4 of the definition.
EXAMPLE 5.1
Describe the following sets by regular expressions: (a) {101 L (b) {abba},
(c'{OL 1O}, (d) {A. ab}, (e) {abb. a, b, bba}, (f) {A, 0, 00, 000.... J, and
(g) {1, 1L 11 L ... }.
Solution
(a) Now. {l}. {OJ are represented by 1 and O. respectively. 101 is obtained
by concatenating L 0 and L So. {1O I} is represented by 101.
Notes: (1) We use x for a regular expression just to distinguish it from the
symbol (or string) x.
(2) The parentheses used in Rule 5 influence the order of evaluation of
a regular expression.
(3) In the absence of parentheses, we have the hierarchy of operations as
follows: iteration (closure). concatenation, and union. That is, in evaluating a
regular expression involving various operations. we perform iteration first, then
concatenation. and finally union. This hierarchy is similar to that followed for
arithmetic expressions (exponentiation. multiplication and addition).
DefInition 5.1 Any set represented by a regular expression is called a regular
set.
If for example, a, bEL. then (i) a denotes the set {a}, (ii) a + b denotes
{a, b}, (iii) ab denotes {ab}, (iv) a* denotes the set {A. a, aa. aaa, ... } and
(v) (a + b)* denotes {a, b}*.
The set represented by R is denoted by L(R),
Now we shall explain the evaluation procedure for the three basic
operations. Let R j and R: denote any two regular expressions. Then (i) a
string in L(R j + R:) is a string from R] or a string from R:; (ii) a string in
L(R j R 2 ) is a string from R j followed by a string from R,. and (iii) a string
in L(R*) is a string obtained by concatenating 11 elements for some II 2: O.
Consequently. (i) the set represented by R j + R 2 is the union of the sets
represented by R] and R 2 • (ii) the set represented by RjR: is the concatenation
of the sets represented by R j and R:. (Recall that the concatenation AB of sets
A and B of strings over I is given by AB = {H'(W: IWj E A, 1~': E B}, and
(iii) the set represented by R* is {WI"': ... It',JWi is in the set represented by
Rand Il 2: O.} Hence.
L(R j + R 2 ) = L(R]) u L(R 2 ),
L(R]R:) = L(RI)L(R:)
L(R*) = (L(R»)*
Also.
L(R*) = (L(R)* = U L(R)"
11=0
L(0) = 0,
L(a) = {a}.
Note: By the definition of regular expressions, the class of regular sets over
I is closed under union, concatenation and closure (iteration) by the conditions
2. 3. 4 of the definition.
EXAMPLE 5.1
Describe the following sets by regular expressions: (a) {101 L (b) {abba},
(c'{OL 1O}, (d) {A. ab}, (e) {abb. a, b, bba}, (f) {A, 0, 00, 000.... J, and
(g) {1, 1L 11 L ... }.
Solution
(a) Now. {l}. {OJ are represented by 1 and O. respectively. 101 is obtained
by concatenating L 0 and L So. {1O I} is represented by 101.