DHARM
REGULAR EXPRESSIONS 213
language L(r 1 ) ∪ L(r 2 ). This property of regular expression is known as ‘addition
property of regular expressions’.†
- If r 1 and r 2 are two regular expressions, and their languages are L( r 1 ) and L(r 2 )
respectively, then (r 1. r 2 ) will also be a regular expression and it generates the
language L(r 1 ). L(r 2 ). This property of regular expression is known as ‘concatenation
property of regular expressions’.‡
- If r be a regular expression, and its language is L(r), then r will also be a regular
expression and it denotes the language L(r) or L(r). This property of regular
expression is called ‘Kleeny closure property of regular expression’ where, L(r) is
Kleeny closure of language L, i.e.,
Let L(r) = L,
then L = ∀≥∪i 0 Li
= L^0 ∪ L^1 ∪ L^2 ∪ .............∪ Li ∪ Li+1 ∪.................∞
where L^0 = {∈} [language contains null string]
L^1 = L. L^0 = L. {∈} = L;
L^2 = L. L^1 ;
L^3 = L. L^2 ;
.....................
.....................
Li = L. Li–1;
.....................
For example, if a is the regular expression then its language will be given by L(a)
where, L(a) = {a} then,
L(a) = {∈, a, aa, aaa, ..............∞}.
- Nothing else is regular expression.
In the definition of regular expression we have discussed the nature of regular expres-
sion over following operators i.e.,
l + (addition) or ∪ (union),
l (Concatenation), and
l ∗ (Kleeny closure)
So for the study of regular expressions over these operators and the language generated
by these composite regular expressions, the precedence of operators is important, i.e., *,. , +
is the sequence of precedence from higher to lower.
Example 9.1. Now we discuss various regular expressions formed over Σ = {0, 1} and see the
importance of operators precedence while we enumerate the language from the composite regu-
lar expression.
† For example let L 1 = {00, 10} and L 2 = {0, 1, 00} then addition of two languages is,
L 1 ∪ L 2 = {0, 1, 00, 10},
If L 1 ′ = {∈, 00, 10} then its addition with language L 2 will be,
L 1 ′ ∪ L 2 = {∈, 0, 1, 00, 10}
‡ The concatenation of L 1 and L 2 is given as,
L 1. L 2 = {000, 001, 0000, 100, 101, 1000} and,
Concatenation with L 1 ′ is,
L 1 ′. L 2 = {0, 1, 00, 000, 001, 0000, 100, 101, 10000}.
