Regular expression in theory of computation solved examples Part – 2

Solution:

We have the input alphabet ∑ = {a, b, c}

Here, the resultant regular expression will denote the set of all strings which contain at least one occurrence of each symbol in {a, b, c}, i.e., the resultant regular expression should denote the strings such as abc, bcaa, ccbaa, baacc, bbaaccc, .. .. .. .. and many more in which there is atleast one a, one b and one c.

But, for this, we have to face a problem. The problem here is that we cannot assume that symbols over the given input alphabets ∑ are in any particular order. Thus, here we have no way of saying “in any order”. So, first of all, we have to list out the smallest possible order of symbols over the given ∑, that is-

abc + acb + bac + cab + cba                            (1)

Here, in the expression, ‘+’ denotes ‘or’ as mentions in previous problems.

Since, we required all stings which contain atleast one occurrence of each symbol of given ∑. Thus, we must have to allow the arbitrary regular expression which represents any string at all over the given ∑ at place which we marked by ‘X’, in below expression-

X a X b X c X + X a X c X b X + X b X a X c X + X c X a X b X + X c X b X a X          (2)

Here, the regular expression for the places X can be written as-

            (a + b + c)*

i.e., the regular expression over the given input alphabet ∑ which contain any string at all.

Thus, putting this regular expression at the places marked by X’s in the form of resultant regular expression given in the expression (2), we will get-

(a + b + c)* a (a + b + c)* b (a + b + c)* c (a + b + c)* +
(a + b + c)* a (a + b + c)* c (a + b + c)* b (a + b + c)* +
(a + b + c)* b (a + b + c)* a (a + b + c)* c (a + b + c)* +
(a + b + c)* c (a + b + c)* a (a + b + c)* b (a + b + c)* +
(a + b + c)* c (a + b + c)* b (a + b + c)* a (a + b + c)*

This is the required resultant regular expression.