DHARMREGULAR EXPRESSIONS 215
(0 + 1)*. 0 or 0. (0 + 1)* ⇒ (0 + 1)*. 0. (0 + 1)*
where, L[( 0 + 1 )*. 0. ( 0 + 1 )*] = {0, 00, 01, 000,............};
2.The set of all strings containing at least one 0 or at least one 1.
Since the regular expression (0 + 1) generates the language either 0 or 1. So, if
(0 + 1) is concatenated with another regular expression (0 + 1)* then resulting
regular expression i.e.,
( 0 + 1 ). ( 0 + 1 )* or ( 0 + 1 )*. ( 0 + 1 ) ⇒ ( 0 + 1 )*. ( 0 + 1 ). ( 0 + 1 )* will generates the
language L[( 0 + 1 )*. ( 0 + 1 ). ( 0 + 1 )*] where,
L((0 + 1)* (0 + 1) (0 + 1)*) = {0, 00, 01, ......,1, 10, 11,......};
3.The set of all strings containing at least one 0 and at least one 1.
From 1 we see that regular expression (0 + 1)*. 0. (0 + 1)* produces the language
that consists of all strings of 0’s and 1’s with confirmation of at least a single 0. If this
regular expression concatenate with 1 then resulting regular expression i.e.,
(0 + 1)*. 0. 1. (0 + 1)* or (0 + 1)*. 1. 0. (0 + 1)*
⇒ (0 + 1)*. (1. 0 + 0. 1). (0 + 1)*
will generates the language which confirms the presence of at least one 0 and at
least one 1. Hence, the language is L = {01, 10, 001, 100, 010, 101, 011, 110, .........}
4.The set of all strings of even length.
Since, the strings of minimum length which is even are {00, 01, 10, 11} thus the
corresponding regular expression will be (0 0 + 0 1 + 1 0 + 1 1). The next string of
higher even length can be obtained from the concatenation of strings of minimum
length 2 with zero /more times, i.e.,
(0 0 + 0 1 + 1 0 + 1 1)*. (0 0 + 0 1 + 1 0 + 1 1)
⇒ (0 0 + 0 1 + 1 0 + 1 1)+
Alternatively, (0 0 + 0 1 + 1 0 + 1 1) can also be written as [(0 + 1). (0 + 1)], hence
(0 0 + 0 1 + 1 0 + 1 1)+ can be written as [(0 + 1). (0 + 1)]+
5.The set of all strings of length ≤≤≤≤≤ 5.
First we form the regular expression that generates the language consists of all strings
of length 5 i.e.,
(0 + 1). (0 + 1). (0 + 1). (0 + 1). (0 + 1)
We can reduce the length of the strings below five by introducing the null string in
each of the regular expression. Thus the resulting regular expression will be given
as, (0 + 1 + ∈∈∈∈∈). (0 + 1 + ∈∈∈∈∈). (0 + 1 + ∈∈∈∈∈). (0 + 1 + ∈∈∈∈∈). (0 + 1 + ∈∈∈∈∈)
6.The set of all strings which ends with 1 and doesn’t contain the substring 00.
The minimum length strings satisfy this condition are {1, 01, 11, 101, 011, ......}. For
the 1st and 2nd string of the language set the regular expression will be (1 + 0 1).
Kleeny closure of this regular expression i.e., (1 + 0 1)* produces all string formed
over {1, 01} i.e., {∈, 1, 01, 101, 011, .....}. Since, ∈ is not in the language, hence to drop
the possibility of string ∈ we take the positive closure† of regular expression i.e.,
(1 + 0 1)+ or (1 + 0 1)*. (1 + 0 1)
which generates the language {1, 01, 11, 101, ......}.† Positive closure property of regular expression says that if r is the regular expression then r+
will also be the regular expression, where r+ is defined as,
r+ = r. r or r. r