DHARM214 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE(a)( 0 + 1 ) is a regular expression, which generates the language {0, 1}. Because, L(0 ) = {0}
and L( 1 ) = {1} and the addition of language i.e.,
L( 0 + 1 ) = L( 0 ) ∪ L( 1 ) = {0, 1}; (which is either 0 or 1)
(b)( 0. 1 ) is a regular expression, which generates the language {0, 01, 011, 0111,....}.
Here, we assume regular expression r 1 = 0 and r 2 = 1 so L(r 1 ) = {0} and L(r 2 ) = {∈, 1,
11, 111, ......∞}. Therefore, the language generated by concatenation of regular ex-
pressions r 1. r 2 will be L(r 1. r 2 ) i.e.,
L(r 1. r 2 ) = L(r 1 ). L(r 2 ) = {0, 01, 011, 0111, .........∞}
(c)( 0 + 1 ) is a regular expression, that generates the language which is the union of set
of all strings formed by regular expressions 0 or 1 i.e., L( 0 ) ∪ L( 1 ),
where, L( 0 ) = {0} and L( 1 ) = {∈, 1, 11, 111,........} hence,
L( 0 ) ∪ L( 1 ) = {∈, 0, 1, 11, 111, ......}.
(d)( 0 + 1 ) is a regular expression, so its language is the set of all strings formed using
symbol 0 or 1. Here we assume regular expression r = ( 0 + 1 ) then L(r) = {0, 1}.
Therefore, L(r) = L = L^0 ∪ L^1 ∪ L^2 ∪ L^3 ......... where L^0 = {∈}; L^1 = L. L^0 = ∈. {0,
1} = {0, 1}; L^2 = L. L^1 = {0, 1}. {0, 1} = {00, 01, 10, 11}; L^3 = L. L^2 = {0, 1}. {00, 01, 10,
11} = {000, 001, 010, 011, 100, 101, 110, 111}; .....and so on.
Hence, L = {∈, 0, 1, 00, 01, 10, 11, 000, .......} or set of all possible strings formed over
symbols 0’s & 1’s including the null string.
(e)(0. 1. 1. 0) is a regular expression and its language will be L(0. 1. 1. 0). Since,
L(0) = {∈, 0, 00, 000,...}; L( 1 ) = {1}; again L( 1 ) = {1}; and L(0) = {∈, 0, 00, 000, ......}
therefore,
L(0. 1. 1. 0) = {∈, 0, 00,...}.{1}.{1}.{∈, 0, 00, .....}
= {11 (when first and last RE† produces ∈), 011, 0011, ....(when first RE produces
multiple 0’s and last RE produces ∈), 110, 1100, ...(when first RE produces ∈ and
last RE produces multiple 0’s), 0110, 01100, ..., 00110, 001100, .............∞}.
Hence, language contains all strings of 0’s having two consecutive 1’s.
(f) For the regular expression (0 + 1). 1. 0. 1. (0 + 1) the language will be the set of
all strings formed over 0’s and 1’s consisting of pattern 101. Since the presence of RE
first and last produces all the strings of 0’s and 1’s including ∈ but the essential part
of all the strings must be the presence of the substring 101 which is produced by the
concatenation of RE 2nd, 3rd and 4th.
Note that if the regular expression is constructed for the language consisting of the string x, then
its regular expression will be denoted by x.
In the previous example we saw how regular languages are to be generated from the
given regular expressions. In the next example we will see how the regular expressions are
constructed from given regular languages
Example 9.2. Consider regular languages are defined over {0, 1} then write regular expressions
for following regular languages.
1.The set of all strings containing at least one 0.
Since, we have seen previously that, regular expression (0 + 1) generates set of all
strings over {0, 1}. For the occurrence of at least one zero in the set of all possible
strings, regular expression (0 + 1)* will be concatenate with another regular expres-
sion 0. Therefore, regular expression will be,
† RE stands for regular expression